Add One Row To Tree Problem

Description

LeetCode Problem 623.

Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth.

Note that the root node is at depth 1.

• Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur’s left subtree root and right subtree root.
• cur’s original left subtree should be the left subtree of the new left subtree root.
• cur’s original right subtree should be the right subtree of the new right subtree root.
• If depth == 1 that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root’s left subtree.

Example 1:

``````1
2
Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]
``````

Example 2:

``````1
2
Input: root = [4,2,null,3,1], val = 1, depth = 3
Output: [4,2,null,1,1,3,null,null,1]
``````

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].
• The depth of the tree is in the range [1, 10^4].
• -100 <= Node.val <= 100
• -10^5 <= val <= 10^5
• 1 <= depth <= the depth of tree + 1

Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int v, int d) {
if (d == 1) {
TreeNode* newroot = new TreeNode(v);
newroot->left = root;
return newroot;
}
else if (d == 0) {
TreeNode* newroot = new TreeNode(v);
newroot->right = root;
return newroot;
}

if (!root) {
return nullptr;
}
else if (d == 2) {
return root;
}
else if (d > 2) {
root->left  = addOneRow(root->left,  v, d - 1);
root->right = addOneRow(root->right, v, d - 1);
}
return root;
}
};
``````