LeetCode-617. 合并二叉树

问题地址

LeetCode每日一题/2020-09-23

LeetCode617. 合并二叉树

问题描述

规则

• 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
  你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例

• 示例一：

输入: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7    
输出: 
合并后的树:
         3
        / \
       4   5
      / \   \ 
     5   4   7

注意

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

解析

解题思路

• 题目要求必须从两个树的根节点开始，最直观的想法是采用前序遍历。

数据操作分析

• 在合并二叉树时，两个二叉树对应节点可能存在如下情况：
  • t1、t2对应节点不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和。
  • t1、t2对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
  • t1、t2对应节点均为空，则合并后的二叉树的对应节点也为空；

复杂度分析

1. 时间复杂度
2. 空间复杂度

编码实现

public class LeetCode0617_MergeTwoBinaryTrees {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        TreeNode res = new TreeNode(t1.val + t2.val);
        res.left = mergeTrees(t1.left, t2.left);
        res.right = mergeTrees(t1.right, t2.right);
        return res;
    }
}

官方解法

方法一：深度优先搜索

思路：

• 可以使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。
  • 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
  • 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
  • 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。
• 对一个节点进行合并之后，还要对该节点的左右子树分别进行合并。这是一个递归的过程。
  

复杂度分析：

1. 时间复杂度:O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会对该节点进行显性合并操作，因此被访问到的节点数不会超过较小的二叉树的节点数。

2. 空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。

编码实现

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }
}

方法二：广度优先搜索

思路：

• 也可以使用广度优先搜索合并两个二叉树。首先判断两个二叉树是否为空，如果两个二叉树都为空，则合并后的二叉树也为空，如果只有一个二叉树为空，则合并后的二叉树为另一个非空的二叉树。
• 如果两个二叉树都不为空，则首先计算合并后的根节点的值，然后从合并后的二叉树与两个原始二叉树的根节点开始广度优先搜索，从根节点开始同时遍历每个二叉树，并将对应的节点进行合并。
• 使用三个队列分别存储合并后的二叉树的节点以及两个原始二叉树的节点。初始时将每个二叉树的根节点分别加入相应的队列。每次从每个队列中取出一个节点，判断两个原始二叉树的节点的左右子节点是否为空。如果两个原始二叉树的当前节点中至少有一个节点的左子节点不为空，则合并后的二叉树的对应节点的左子节点也不为空。对于右子节点同理。
• 如果合并后的二叉树的左子节点不为空，则需要根据两个原始二叉树的左子节点计算合并后的二叉树的左子节点以及整个左子树。考虑以下两种情况：
  • 如果两个原始二叉树的左子节点都不为空，则合并后的二叉树的左子节点的值为两个原始二叉树的左子节点的值之和，在创建合并后的二叉树的左子节点之后，将每个二叉树中的左子节点都加入相应的队列；
  • 如果两个原始二叉树的左子节点有一个为空，即有一个原始二叉树的左子树为空，则合并后的二叉树的左子树即为另一个原始二叉树的左子树，此时也不需要对非空左子树继续遍历，因此不需要将左子节点加入队列。
• 对于右子节点和右子树，处理方法与左子节点和左子树相同。
  

复杂度分析：

1. 时间复杂度:O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数。对两个二叉树同时进行广度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数。

2. 空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数。空间复杂度取决于队列中的元素个数，队列中的元素个数不会超过较小的二叉树的节点数。

编码实现

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue.offer(merged);
        queue1.offer(t1);
        queue2.offer(t2);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
            TreeNode left1 = node1.left, left2 = node2.left, right1 = node1.right, right2 = node2.right;
            if (left1 != null || left2 != null) {
                if (left1 != null && left2 != null) {
                    TreeNode left = new TreeNode(left1.val + left2.val);
                    node.left = left;
                    queue.offer(left);
                    queue1.offer(left1);
                    queue2.offer(left2);
                } else if (left1 != null) {
                    node.left = left1;
                } else if (left2 != null) {
                    node.left = left2;
                }
            }
            if (right1 != null || right2 != null) {
                if (right1 != null && right2 != null) {
                    TreeNode right = new TreeNode(right1.val + right2.val);
                    node.right = right;
                    queue.offer(right);
                    queue1.offer(right1);
                    queue2.offer(right2);
                } else if (right1 != null) {
                    node.right = right1;
                } else {
                    node.right = right2;
                }
            }
        }
        return merged;
    }
}

精彩评论

跳转地址1：617. 合并二叉树:【三种递归】【一种迭代】详解

思路：

• 相信这道题目很多同学疑惑的点是如何同时遍历两个二叉树呢？其实和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作。那么前中后序应该使用哪种遍历呢？本题使用哪种遍历都是可以的！我们下面以前序遍历为例。动画如下：
  

• 那么我们来按照递归三部曲来解决：

  • 确定递归函数的参数和返回值：
    • 首先那么要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。代码如下：

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) 

- 确定终止条件：
    - 因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果`t1 == NULL` 了，两个树合并就应该是 t2 了啊（如果t2也为NULL也无所谓）。反过来如果`t2 == NULL`，那么两个数合并就是t1（如果t1也为NULL也无所谓）。代码如下：

if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1

- 确定单层递归的逻辑：
    - 单层递归的逻辑就比较好些了，这里我们用重复利用一下t1这个树，t1就是合并之后树的根节点（所谓的修改了元数据的结构）。那么单层递归中，就要把两棵树的元素加到一起。

t1->val += t2->val;

    - 那么此时t1 的左子树 应该是 合并 t1左子树 t2左子树之后的左子树，t1 的右子树 应该是 合并 t1右子树 t2右子树之后的右子树。代码如下：

        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;

编码实现

• 此时前序遍历，修改原输入树结构的完整代码就写出来了，如下：

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->val += t2->val;                             // 中
        t1->left = mergeTrees(t1->left, t2->left);      // 左
        t1->right = mergeTrees(t1->right, t2->right);   // 右
        return t1;
    }
};

• 那么中序遍历可不可以呢，也是可以的，代码如下：

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->left = mergeTrees(t1->left, t2->left);      // 左
        t1->val += t2->val;                             // 中
        t1->right = mergeTrees(t1->right, t2->right);   // 右
        return t1;
    }
};

• 后序遍历呢，依然可以，代码如下：

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
        if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
        // 修改了t1的数值和结构
        t1->left = mergeTrees(t1->left, t2->left);      // 左
        t1->right = mergeTrees(t1->right, t2->right);   // 右
        t1->val += t2->val;                             // 中
        return t1;
    }
};

跳转地址2：动画演示 递归+迭代 617.合并二叉树

解法一：递归实现

• 如果没有头绪的话，可以将这两颗树想象成是两个数组：

1 3 2 5
2 1 3 4 7

• 合并两个数组很直观，将数组2的值合并到数组1中，再返回数组1就可以了。
  对于二叉树来说，如果我们像遍历数组那样，挨个遍历两颗二叉树中的每个节点，再把他们相加，那问题就比较容易解决了。
• 遍历二叉树很简单，用前序遍历就可以了，再依次把访问到的节点值相加，因为题目没有说不能改变树的值和结构，我们不用再创建新的节点了，直接将树2合并到树1上再返回就可以了。
  需要注意：这两颗树并不是长得完全一样，有的树可能有左节点，但有的树没有。
  对于这种情况，我们统一的都把他们挂到树1 上面就可以了，对于上面例子中的两颗树，合并起来的结果如下：

         3
        / \
       4   5
      / \   \ 
     5   4   7

• 相当于树1少了一条腿，而树2有这条腿，那就把树2的拷贝过来。总结下递归的条件：
  • 终止条件：树1的节点为null，或者树2的节点为null
  • 递归函数内：将两个树的节点相加后，再赋给树1的节点。再递归的执行两个树的左节点，递归执行两个树的右节点
• 动画演示如下：
  

时间复杂度分析

1. 时间复杂度：O(N)
2. 空间复杂度：O(h)，h是树的高度

编码实现

 class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1==null || t2==null) {
            return t1==null? t2 : t1;
        }
        return dfs(t1,t2);
    }

    TreeNode dfs(TreeNode r1, TreeNode r2) {
        // 如果 r1和r2中，只要有一个是null，函数就直接返回
        if(r1==null || r2==null) {
            return r1==null? r2 : r1;
        }
        //让r1的值 等于  r1和r2的值累加，再递归的计算两颗树的左节点、右节点
        r1.val += r2.val;
        r1.left = dfs(r1.left,r2.left);
        r1.right = dfs(r1.right,r2.right);
        return r1;
    }
}

解法二：递归实现

• 迭代实现用的是广度优先算法，广度优先就需要额外的数据结构来辅助了，我们可以借助栈或者队列来完成。
• 只要两颗树的左节点都不为null，就把将他们放入队列中；同理只要两棵树的右节点都不为null了，也将他们放入队列中。
• 然后我们不断的从队列中取出节点，把他们相加。
• 如果出现 树1的left节点为null，树2的left不为null，直接将树2的left赋给树1就可以了；同理如果树1的right节点为null，树2的不为null，将树2的right节点赋给树1。
• 动画图如下：
  

时间复杂度分析

1. 时间复杂度：O(N)
2. 空间复杂度:O(N)，对于满二叉树时，要保存所有的叶子节点，即N/2个节点。

编码实现

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    //如果 t1和t2中，只要有一个是null，函数就直接返回
        if(t1==null || t2==null) {
            return t1==null? t2 : t1;
        }
        java.util.LinkedList<TreeNode> queue = new java.util.LinkedList<TreeNode>();
        queue.add(t1);
        queue.add(t2);
        while(queue.size()>0) {
            TreeNode r1 = queue.remove();
            TreeNode r2 = queue.remove();
            r1.val += r2.val;
            //如果r1和r2的左子树都不为空，就放到队列中
            //如果r1的左子树为空，就把r2的左子树挂到r1的左子树上
            if(r1.left!=null && r2.left!=null){
                queue.add(r1.left);
                queue.add(r2.left);
            }
            else if(r1.left==null) {
                r1.left = r2.left;
            }
            //对于右子树也是一样的
            if(r1.right!=null && r2.right!=null) {
                queue.add(r1.right);
                queue.add(r2.right);
            }
            else if(r1.right==null) {
                r1.right = r2.right;
            }
        }
        return t1;
    }
}