What is the main idea behind Merge Two Binary Trees?

Traverse both trees simultaneously, sum values for overlapping nodes, and keep non-null nodes when only one exists.

Should I use DFS or BFS to merge two binary trees?

Both DFS and BFS work; DFS is simpler recursively, BFS works iteratively and helps visualize level-wise merging.

How do I handle empty input trees?

If one or both roots are null, return the non-null root or null if both are empty, ensuring the merge is valid.

Can this method handle unbalanced trees?

Yes, by recursively or iteratively checking for null children, you can merge unbalanced trees without losing any subtree.

Does GhostInterview track the Binary-tree traversal pattern?

Yes, it highlights traversal and state tracking, helping you avoid common mistakes when merging overlapping and non-overlapping nodes.

#617

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

合并二叉树

给你两棵二叉树： root1 和 root2 。想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树…

树深度优先搜索广度优先搜索二叉树

题目描述

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

提示：

两棵树中的节点数目在范围 [0, 2000] 内
-10⁴ <= Node.val <= 10⁴

lightbulb

解题思路

方法一：递归

递归合并两棵树的节点。

如果其中一棵树的当前节点为空，则返回另一棵树的当前节点作为合并后节点。
如果两棵树的当前节点都不为空，则将它们的值相加作为合并后节点的新值，然后递归合并它们的左右子节点。

时间复杂度 $O(m)$ ，空间复杂度 $O(m)$ 。其中 $m$ 是两棵树的节点数的最小值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(
        self, root1: Optional[TreeNode], root2: Optional[TreeNode]
    ) -> Optional[TreeNode]:
        if root1 is None:
            return root2
        if root2 is None:
            return root1
        node = TreeNode(root1.val + root2.val)
        node.left = self.mergeTrees(root1.left, root2.left)
        node.right = self.mergeTrees(root1.right, root2.right)
        return node

speed

复杂度分析

指标	值
时间	complexity is O(min(N1,N2)) where N1 and N2 are the number of nodes in root1 and root2 since each pair is processed once. Space complexity is O(H) for DFS recursion stack or O(W) for BFS queue, with H as tree height and W as maximum width of the trees.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you handle null nodes correctly during traversal?
question_mark
Can you explain why DFS and BFS both work for merging trees?
question_mark
How do you manage space when merging large unbalanced trees?

warning

常见陷阱

外企场景

error
Forgetting to return non-null nodes when the other tree has null children.
error
Overwriting existing subtrees instead of summing overlapping nodes.
error
Ignoring edge cases with completely empty input trees.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Merge multiple binary trees instead of two, generalizing DFS/BFS merging.
arrow_right_alt
Merge trees but keep maximum value instead of sum at overlapping nodes.
arrow_right_alt
Perform merge while maintaining additional attributes per node, like color or weight.

help

常见问题

外企场景

继续练习

#623 在二叉树中增加一行 #637 二叉树的层平均值 #653 两数之和 IV - 输入二叉搜索树