ACM 选手图解 LeetCode 合并二叉树-阿里云开发者社区

大家好呀，我是帅蛋。

今天解决合并二叉树，将两棵二叉树根据给出的规则合并成一棵二叉树。

咱们话不多说，直接开整。

LeetCode 617：合并二叉树

题意

给定两棵二叉树 root1 和 root2，合并成一棵新的二叉树，合并规则为：

如果两个节点重叠，将两个节点的值相加作为合并后节点的新值，否则，不为 null 的节点将直接作为新二叉树的节点。

示例

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

输出：[3,4,5,5,4,null,7]

提示

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

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

题目解析

难度简单，二叉树遍历解法经典题目。

合并二叉树这道题，具体做法其实都已经在描述里了，其实就是分两种情况讨论：

如果两棵树对应位置上都有节点，则新节点的值为两个节点的值相加。
如果两棵树对应位置上只有一个节点有值，则新节点的值就为该节点的值。

其实就是遍历两棵二叉树，在这个过程中遵守上面的两种情况即可。

我用颜色稍微标记一下，可能看的更清楚一些：

递归法

递归法就是老套路，根据【递归算法】文章中讲的，实现递归，需要两步：

找出重复的子问题（递推公式）。
终止条件。

(1) 找出重复的子问题。

这个在上面看图的时候其实已经找出来了。

对于每一层来说，就是重新创建一个节点 root 存储 root1.val + root2.val。

之后 root 的左子树就是合并 root1 左子树和 root2 左子树之后的左子树，root 的右子树就是合并 root1 右子树和 root2 右子树之后的右子树。

# 如果都存在节点，创建一个新的节点存储合并后的值
root = TreeNode(root1.val + root2.val)
# 递归合并左子树
root.left = self.mergeTrees(root1.left, root2.left)
# 递归合并右子树
root.right = self.mergeTrees(root1.right, root2.right)

你看这种先根节点再左子树最后右子树的方式是不是很眼熟？这就是我们学的前序遍历。

当然像中序遍历或者后序遍历的方式都是可以的，我在这就不多赘述，大家可以自己写着试试。

(2) 确定终止条件。

对于中止条件的话，在本题中就是：

对于遍历的两棵二叉树 root1 和 root2，如果 root1 的节点为空，那合并之后就应该是 root2，同样如果 root2 的节点为空，那合并之后就应该是 root1。

// 如果 root1 为空，则合并之后节点为 root2
if(root1 == null){
    return root2;
}
// 如果 root2 为空，则合并之后节点为 root1
if(root2 == null){
    return root1;
}

递归二步曲确定完了，这道题的代码其实也就做出来了。

Python 代码实现

# 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: TreeNode, root2: TreeNode) -> TreeNode:
        # 如果 root1 为空，则合并之后节点为 root2
        if root1 == None:
            return root2
        # 如果 root2 为空，则合并之后节点为 root1
        if root2 == None:
            return root1
        # 如果都存在节点，创建一个新的节点存储合并后的值
        root = TreeNode(root1.val + root2.val)
        # 递归合并左子树
        root.left = self.mergeTrees(root1.left, root2.left)
        # 递归合并右子树
        root.right = self.mergeTrees(root1.right, root2.right)
        return root

Java 代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 如果 root1 为空，则合并之后节点为 root2
        if(root1 == null){
            return root2;
        }
        // 如果 root2 为空，则合并之后节点为 root1
        if(root2 == null){
            return root1;
        }
        // 如果都存在节点，创建一个新的节点存储合并后的值
        TreeNode root = new TreeNode(root1.val + root2.val);
        // 递归合并左子树
        root.left = mergeTrees(root1.left, root2.left);
        // 递归合并右子树
        root.right = mergeTrees(root1.right, root2.right);
        return root;
    }
}

假设 root1 的节点数为 n，root2 的节点数为 m，对于两棵二叉树而言，只有对应的节点都不为空时才会进行合并操作，所以合并的时候一定是遍历完了节点数相对较少的二叉树，所以总的时间复杂度为O(min(n,m))。

此外在递归过程中调用了额外的栈空间，栈的大小取决于二叉树的高度，二叉树 root1 最坏情况下的高度为 n，二叉树 root2 最坏情况下的高度为 m，所以空间复杂度为 O(min(n,m))。

非递归法（迭代）

在递归法中，我们在找重复子问题的时候，对于每一层来说，都是看 root1 的左子树和 root2 的左子树，以及 root1 的右子树和 root2 的右子树。

这种一层层的看下去有点类似层次遍历。

我在【层次遍历】文章中说过，非递归版的层次遍历用的则是队列，这是由于层次遍历的属性非常契合队列的特点。

在本题中，具体的做法就是维护两个队列，队列 queueMerge 存储合并后的树节点，queue 则是 root1 和 root2 的节点，具体做法我们来图解。

比如对于下图，左边是 root1，右边是 root2：

首先我们先创建一个新的根节点 root，其值为 root1.val + root2.val，同时初始化两个队列，将 root 入 queueMerge 队列，将 root1 和 root2 入 queue 队列。

# 如果都存在节点，创建一个新的节点存储合并后的值
root = TreeNode(root1.val + root2.val)
# 初始化队列
queueMerge = [root]
queue = [root1, root2]

此时队列不为空，将 queueMerge 队首元素出队列，此时 node = 3，同时将 queue 两个队首元素出队列，此时 node1 = 1，node2 = 2。

对于 node1 和 node2，都存在左孩子，根据题目的描述，node 的左孩子为 node1 左孩子的值 + node2 左孩子的值。

同时将 node 的左孩子入 queueMerge 队列，将 node1 的左孩子和 node2 的左孩子入 queue 队列。

# 从队列中取出当前节点
node = queueMerge.pop(0)
node1 = queue.pop(0)
node2 = queue.pop(0)
if node1.left or node2.left:
    # 若两棵树的左孩子都存在
    if node1.left and node2.left:
        leftMerge = TreeNode(node1.left.val + node2.left.val)
        node.left = leftMerge
        queueMerge.append(leftMerge)
        queue.append(node1.left)
        queue.append(node2.left)

同样，对于 node1 和 node2 来说，都存在右孩子，根据题目的描述，node 的右孩子为 node1 右孩子的值 + node2 右孩子的值。

同时将 node 的右孩子入 queueMerge 队列，将 node1 的右孩子和 node2 的右孩子入 queue 队列。

if node1.right or node2.right:
    # 若两棵树的右孩子都在
    if node1.right and node2.right:
        rightMerge = TreeNode(node1.right.val + node2.right.val)
        node.right = rightMerge
        queueMerge.append(rightMerge)
        queue.append(node1.right)
        queue.append(node2.right)

队列不为空，继续出队列，root = 4，root1 = 3， root2 = 1。

此时 root1 有左孩子，root2 没有左孩子，则 root 的左孩子直接为 root1 的左孩子。

elif node1.left:
    node.left = node1.left

同时此时 root1 没有右孩子，root2 有右孩子，则 root 的右孩子直接为 root2 的右孩子。

elif node2.right:
    node.right = node2.right

接下来就是重复上面的操作，直至队列为空，返回最后的结果。

Python 代码实现

# 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: TreeNode, root2: TreeNode) -> TreeNode:
        # 如果 root1 为空，则合并之后节点为 root2
        if root1 == None:
            return root2
        # 如果 root2 为空，则合并之后节点为 root1
        if root2 == None:
            return root1
        # 如果都存在节点，创建一个新的节点存储合并后的值
        root = TreeNode(root1.val + root2.val)
        # 初始化队列
        queueMerge = [root]
        queue = [root1, root2]
        while queue:
            # 从队列中取出当前节点
            node = queueMerge.pop(0)
            node1 = queue.pop(0)
            node2 = queue.pop(0)
            if node1.left or node2.left:
                # 若两棵树的左孩子都存在
                if node1.left and node2.left:
                    leftMerge = TreeNode(node1.left.val + node2.left.val)
                    node.left = leftMerge
                    queueMerge.append(leftMerge)
                    queue.append(node1.left)
                    queue.append(node2.left)
                # 若只有一棵树存在左孩子，直接赋值
                elif node1.left:
                    node.left = node1.left
                elif node2.left:
                    node.left = node2.left
            if node1.right or node2.right:
                # 若两棵树的右孩子都在
                if node1.right and node2.right:
                    rightMerge = TreeNode(node1.right.val + node2.right.val)
                    node.right = rightMerge
                    queueMerge.append(rightMerge)
                    queue.append(node1.right)
                    queue.append(node2.right)
                # 若只有一棵树存在右孩子，直接赋值
                elif node1.right:
                    node.right = node1.right
                elif node2.right:
                    node.right = node2.right
        return root

Java 代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 如果 root1 为空，则合并之后节点为 root2
        if(root1 == null){
            return root2;
        }
        // 如果 root2 为空，则合并之后节点为 root1
        if(root2 == null){
            return root1;
        }
        // 如果都存在节点，创建一个新的节点存储合并后的值
        TreeNode root = new TreeNode(root1.val + root2.val);
        // 初始化队列
        Queue<TreeNode> queueMerge = new LinkedList<TreeNode>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queueMerge.offer(root);
        queue.offer(root1);
        queue.offer(root2);
        while(!queue.isEmpty()){
            // 从队列中取出当前节点
            TreeNode node = queueMerge.poll();
            TreeNode node1 = queue.poll(), node2 = queue.poll();
            if(node1.left != null || node2.left != null){
                // 若两棵树的左孩子都存在
                if(node1.left != null && node2.left != null){
                    TreeNode leftMerge = new TreeNode(node1.left.val + node2.left.val);
                    node.left = leftMerge;
                    queueMerge.offer(leftMerge);
                    queue.offer(node1.left);
                    queue.offer(node2.left);
                }
                // 若只有一棵树存在左孩子，直接赋值
                else if(node1.left != null){
                    node.left = node1.left;
                }
                else if(node2.left != null){
                    node.left = node2.left;
                }
            }
            //  若两棵树的右孩子都在
            if(node1.right != null || node2.right != null){
                if(node1.right != null && node2.right != null){
                    TreeNode rightMerge = new TreeNode(node1.right.val + node2.right.val);
                    node.right = rightMerge;
                    queueMerge.offer(rightMerge);
                    queue.offer(node1.right);
                    queue.offer(node2.right);
                }
                // 若只有一棵树存在右孩子，直接赋值
                else if(node1.right != null){
                    node.right = node1.right;
                }
                else if(node2.right != null){
                    node.right = node2.right;
                }
            }
        }
        return root;
    }
}

同样，对于非递归法，它总的时间复杂度为O(min(n,m))，空间复杂度为 O(min(n,m))。

图解合并二叉树到这就结束辣，大家学会了嘛？是不是大喊一声，二叉树遍历，YYDS！

这道题我在写的时候就觉得贼神奇，递归法几行代码，非递归法五六十行，累了累了。

今天就先到这，记得做好总结，还有...本蛋的点赞~

我是帅蛋，我们下次见！

ACM 选手图解 LeetCode 合并二叉树

热门文章

最新文章

相关课程

相关电子书