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
| class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
TreeNode dummy = new TreeNode(0);
dfs(root1, root2, dummy, true);
return dummy.left;
}
private void dfs(TreeNode node1, TreeNode node2, TreeNode prev, boolean isLeft) {
if (node1 == null && node2 == null) {
return;
}
int currVal = node1 != null ? node1.val : 0;
currVal += node2 != null ? node2.val : 0;
TreeNode newNode = new TreeNode(currVal);
if (isLeft) {
prev.left = newNode;
} else {
prev.right = newNode;
}
if (node1 != null && node2 != null) {
dfs(node1.left, node2.left, newNode, true);
dfs(node1.right, node2.right, newNode, false);
} else if (node1 != null) {
dfs(node1.left, null, newNode, true);
dfs(node1.right, null, newNode, false);
} else {
dfs(node2.left, null, newNode, true);
dfs(node2.right, null, newNode, false);
}
}
}
|
