LeetCode 617. 合并二叉树

文章目录

• 前言
• 题目
• 题解
• NO1：深搜DFS
• NO2：BFS(广度优先遍历)
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为LeetCode 热题 HOT 100专题。

---

题目

题目来源leetcode

leetcode地址：617. 合并二叉树，难度：简单。

题目描述(摘自leetcode)：

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

示例 1:
输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7
注意: 合并必须从两个树的根节点开始。

---

题解

NO1：深搜DFS

思路：dfs深搜合并两个树。其中有三种情况：①root1节点为空，直接将root2节点返回。②root2节点为空，直接将root1返回。③root1与root2节点都不为空对应节点值相加，接着往下递归处理左右节点。对于前两种情况一旦出现，其就没有递归下去的必要了，直接返回另一棵子树即可。

代码：时间复杂度O(min(m,n))，空间复杂度O(min(m,n))

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    }
    if (root2 == null) {
        return root1;
    }
    //对于两个节点都不为空
    TreeNode mergeNode = new TreeNode(root1.val + root2.val);
    //合并左右子树
    mergeNode.left = mergeTrees(root1.left, root2.left);
    mergeNode.right = mergeTrees(root1.right, root2.right);
    return mergeNode;
}

---

NO2：BFS(广度优先遍历)

思路：大致思路与递归相同，只不过在这里多使用了三个队列来进行维护树的各个节点。

代码：时间复杂度O(min(m,n))，空间复杂度O(min(m,n))

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    }
    if (root2 == null) {
        return root1;
    }
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
    Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
    TreeNode root = new TreeNode(root1.val + root2.val);
    queue.offer(root);
    queue1.offer(root1);
    queue2.offer(root2);

    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 newNode = new TreeNode(left1.val + left2.val);
                node.left = newNode;
                queue.offer(newNode);
                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 newNode = new TreeNode(right1.val + right2.val);
                node.right = newNode;
                queue.offer(newNode);
                queue1.offer(right1);
                queue2.offer(right2);
            }else if(right1 != null){
                node.right = right1;
            }else if(right2 != null){
                node.right = right2;
            }
        }
    }

    return root;
}

---

参考文章

[1]. leetcode题解

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.12