617. 合并二叉树
题目描述
输入两棵二叉树的根节点 root1 和 root2，用层序数组表示，null 表示空位。
从两个根开始，把两棵树叠放在一起得到一棵新树。在同一位置上，如果两棵树都有节点，新节点的值取两者之和；如果只有一棵树有节点，就直接用这个节点；两边都没有则该位置为空。
返回合并后新树的根节点。
示例 1
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] 输出：[3,4,5,5,4,null,7]
解释：根节点 1 + 2 = 3，其余重叠的位置同样相加，只在一侧出现的节点原样保留。
示例 2
输入：root1 = [1], root2 = [1,2] 输出：[2,2]
解释：根节点相加得 2，左孩子 2 只来自 root2。
数据范围
- 两棵树的节点数都在
[0, 2000]范围内。 -10^4 <= Node.val <= 10^4
解题思路：递归合并
前序递归。merge(a, b)：若 a 为空返回 b，若 b 为空返回 a（只有一边有节点，整棵子树直接拿来用）；否则把 b 的值加到 a 上，再分别合并左子树、右子树，接回 a 的左右指针，返回 a。这样复用 root1 的节点，不必新建。
为什么正确
merge(a, b) 返回的树恰好是以 a 和 b 为根的两棵子树重叠后的结果。
复杂度分析
时间 O(min(n1, n2))，只在两棵树都有节点的位置递归；空间 O(h)，为递归深度。
易错点
当一边为空时要直接返回另一边整棵子树，而不是只拷一个节点；另外必须把递归结果赋回 root1.left / root1.right，否则 root2 独有的分支接不上去。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1:
return root2
if not root2:
return root1
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null)
return root2;
if (root2 == null)
return root1;
root1.val += root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}
}class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (!root1)
return root2;
if (!root2)
return root1;
root1->val += root2->val;
root1->left = mergeTrees(root1->left, root2->left);
root1->right = mergeTrees(root1->right, root2->right);
return root1;
}
};func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
if root1 == nil {
return root2
}
if root2 == nil {
return root1
}
root1.Val += root2.Val
root1.Left = mergeTrees(root1.Left, root2.Left)
root1.Right = mergeTrees(root1.Right, root2.Right)
return root1
}var mergeTrees = function(root1, root2) {
if (!root1)
return root2;
if (!root2)
return root1;
root1.val += root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
};function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
if (!root1)
return root2;
if (!root2)
return root1;
root1.val += root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}其他解法
两种解法都只访问两棵树重叠的节点，一边为空时直接复用另一边的子树；递归简洁，广度优先搜索按层迭代。
解法 2：广度优先搜索 时间 O(min(m, n))，空间 O(min(m, n))
以 root1 为结果。队列中存放成对的节点 (a, b)，两者都非空。取出一对后把 b.val 加到 a.val 上。对左右孩子分别处理：两边都非空就成对入队；a 的孩子为空就直接接上 b 的孩子；b 的孩子为空就保持不变。
不受递归深度限制。需要单独处理“一边为空”的情形，代码比递归长。
from collections import deque
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1:
return root2
if not root2:
return root1
q = deque([(root1, root2)])
while q:
a, b = q.popleft()
a.val += b.val
if a.left and b.left:
q.append((a.left, b.left))
elif not a.left:
a.left = b.left
if a.right and b.right:
q.append((a.right, b.right))
elif not a.right:
a.right = b.right
return root1class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
Deque<TreeNode[]> q = new ArrayDeque<>();
q.offer(new TreeNode[]{root1, root2});
while (!q.isEmpty()) {
TreeNode[] p = q.poll();
TreeNode a = p[0], b = p[1];
a.val += b.val;
if (a.left != null && b.left != null) q.offer(new TreeNode[]{a.left, b.left});
else if (a.left == null) a.left = b.left;
if (a.right != null && b.right != null) q.offer(new TreeNode[]{a.right, b.right});
else if (a.right == null) a.right = b.right;
}
return root1;
}
}class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (!root1) return root2;
if (!root2) return root1;
queue<pair<TreeNode*, TreeNode*>> q;
q.push({root1, root2});
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
a->val += b->val;
if (a->left && b->left) q.push({a->left, b->left});
else if (!a->left) a->left = b->left;
if (a->right && b->right) q.push({a->right, b->right});
else if (!a->right) a->right = b->right;
}
return root1;
}
};func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
if root1 == nil {
return root2
}
if root2 == nil {
return root1
}
q := [][2]*TreeNode{{root1, root2}}
for len(q) > 0 {
a, b := q[0][0], q[0][1]
q = q[1:]
a.Val += b.Val
if a.Left != nil && b.Left != nil {
q = append(q, [2]*TreeNode{a.Left, b.Left})
} else if a.Left == nil {
a.Left = b.Left
}
if a.Right != nil && b.Right != nil {
q = append(q, [2]*TreeNode{a.Right, b.Right})
} else if a.Right == nil {
a.Right = b.Right
}
}
return root1
}var mergeTrees = function(root1, root2) {
if (!root1) return root2;
if (!root2) return root1;
const q = [[root1, root2]];
for (let h = 0; h < q.length; h++) {
const [a, b] = q[h];
a.val += b.val;
if (a.left && b.left) q.push([a.left, b.left]);
else if (!a.left) a.left = b.left;
if (a.right && b.right) q.push([a.right, b.right]);
else if (!a.right) a.right = b.right;
}
return root1;
};function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
if (!root1) return root2;
if (!root2) return root1;
const q: [TreeNode, TreeNode][] = [[root1, root2]];
for (let h = 0; h < q.length; h++) {
const [a, b] = q[h];
a.val += b.val;
if (a.left && b.left) q.push([a.left, b.left]);
else if (!a.left) a.left = b.left;
if (a.right && b.right) q.push([a.right, b.right]);
else if (!a.right) a.right = b.right;
}
return root1;
}