/**
* 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;
}
};