📃 题目描述

题目链接：617. 合并二叉树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

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

🔔 解题思路

递归

所谓合并也就是两个树的对应节点值相加啦，直接递归遍历两棵树就好了（这里需要遍历两棵树，其实和遍历一棵树没什么区别），哪种遍历方式都可以，这里以前序遍历为例：

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return root1 == null ? root2 : 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 上面原地相加：

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return root1 == null ? root2 : 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 == null || root2 == null) {
            return root1 == null ? root2 : root1;
        }
        
        // 辅助队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 根节点入队
        queue.offer(root1);
        queue.offer(root2);
        
        while (!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            
            // 此时两个节点一定不为空，val 相加
            // 直接在 root1 树上操作
            node1.val = node1.val + node2.val;
            
            // 如果两棵树左节点都不为空，加入队列
            if (node1.left != null && node2.left != null) {
                queue.offer(node1.left);
                queue.offer(node2.left);
            }
            
            // 如果两棵树右节点都不为空，加入队列
            if (node1.right != null && node2.right != null) {
                queue.offer(node1.right);
                queue.offer(node2.right);
            }
            
            // 若 node1 的左节点为空，直接赋值
            if (node1.left == null && node2.left != null) {
                node1.left = node2.left;
            }
            
            // 若 node1 的右节点为空，直接赋值
            if (node1.right == null && node2.right != null) {
                node1.right = node2.right;
            }
        }
        return root1;
    }
}

💥 复杂度分析

• 空间复杂度：O(LogN)
• 时间复杂度：O(N)