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
| class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
TreeNode dummy = new TreeNode(0);
dummy.left = root;
dfs(dummy, 0, depth - 1, val);
return dummy.left;
}
private void dfs(TreeNode node, int currDepth, int targetDepth, int val) {
if (node == null) {
return;
}
if (currDepth == targetDepth) {
TreeNode currLeftTree = node.left;
TreeNode currRightTree = node.right;
TreeNode newLeftTree = new TreeNode(val);
TreeNode newRightTree = new TreeNode(val);
node.left = newLeftTree;
newLeftTree.left = currLeftTree;
node.right = newRightTree;
newRightTree.right = currRightTree;
} else {
dfs(node.left, currDepth + 1, targetDepth, val);
dfs(node.right, currDepth + 1, targetDepth, val);
}
}
}
|
DFS即可. 等到到达depth - 1处, new两个node即可, 然后直接返回.
时间复杂度: O(n)
空间复杂度: O(n)
