s4553711
6/22/2017 - 2:34 PM

623.cpp

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if (d == 1) {
            TreeNode* r = new TreeNode(v);
            r->left = root;
            return r;
        }
        return addOneRow(root, v, d, 1);
    }
    TreeNode* addOneRow(TreeNode* root, int v, int d, int cur) {
        if (root == NULL) return NULL;
        if (d == cur+1) {
            TreeNode* tLeft= root->left;
            TreeNode* tRight = root->right;
            TreeNode* nLeft = new TreeNode(v);
            TreeNode* nRight = new TreeNode(v);
            root->left = nLeft;
            root->right = nRight;
            nLeft->left = tLeft;
            nRight->right = tRight;
            return root;
        } else {
            addOneRow(root->left, v, d, cur+1);
            addOneRow(root->right, v, d, cur+1);
        }
        return root;
    }
};