[LeetCode617题合并二叉树] | 刷题打卡

前言

上午的时候写的题解是[LeetCode94题二叉树的中序遍历] | 刷题打卡，这篇题解了给大家简单介绍了二叉树的几种遍历方式，为什么叫前序、中序、后序遍历，有兴趣的或者想要了解的可以先去看下???

题目描述

题目地址: 617. 合并二叉树

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

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

示例 1:

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

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

解题思路

之前[LeetCode94题二叉树的中序遍历] | 刷题打卡中因为题目要求的是中序遍历，所以采用的是中序遍历解答。

这道题给定两个二叉树t1和t2，要合并二叉树，我们就直接用前序遍历来递归实现吧!(这里看你想用哪种递归方式都可以)

在解题过程中我们将t2合并到t1上。

第一步，合并两个二叉树，我们首先要做情况判断，不要一上来就直接开始递归，先对t1和t2进行判断： - t1为空就返回t2，不去管t2是否为空(t2要是空的话返回的也是空，所以这里不用管t2)。 - t2为空就返回t1(经过了上一步的判断t1肯定不为空)。

第二步，经过了判断步骤之后证明t1和t2的节点肯定都不为空，用t1.val + t2.val来覆盖t1.val实现题目中要求重叠节点的值的合并。

第三步，因为我们说用前序遍历来解答，所以这里递归遍历t1和t2的左子树，重复一、二步会取它们左子树的值合并。

第四步，递归遍历t1和t2的右子树，重复一、二步会取它们右子树的值合并。

最后，我们返回t1即可。(因为我们是将t2合并到t1上，所以返回t1)。

解题代码

var mergeTrees = function(t1, t2) {
    if(!t1) return t2;
    if(!t2) return t1;
    t1.val = t1.val + t2.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);
    return t1;
};

刷题打卡记录

这里是之前的刷题打卡记录，大家有兴趣的可以看下，如果有什么不同的见解和看法或者觉得有什么错误的，欢迎在评论区留言！???

[LeetCode0303题区域和检索 - 数组不可变] | 刷题打卡

[LeetCode1200. 最小绝对差] | 刷题打卡

[LeetCode0304题二维区域和检索 - 矩阵不可变] | 刷题打卡

[LeetCode11题盛最多水的容器] | 刷题打卡

[LeetCode0338题比特位计数] | 刷题打卡

[LeetCode209题长度最小的子数组] | 刷题打卡

[LeetCode236题二叉树的最近公共祖先] | 刷题打卡

[LeetCode141题环形链表] | 刷题打卡

[LeetCode53题最大子序和] | 刷题打卡

[LeetCode48题旋转图像] | 刷题打卡

[LeetCode155题最小栈] | 刷题打卡

[LeetCode1124题表现良好的最长时间段] | 刷题打卡

[LeetCode274题H指数] | 刷题打卡

[LeetCode367题有效的完全平方数] | 刷题打卡

[LeetCode1047题删除字符串中的所有相邻重复项] | 刷题打卡

[LeetCode160题相交链表] | 刷题打卡

[LeetCode1438题绝对差不超过限制的最长连续子数组] | 刷题打卡

[LeetCode434题字符串中的单词数] | 刷题打卡

[LeetCode75题颜色分类] | 刷题打卡

[LeetCode513题找树左下角的值] | 刷题打卡

[LeetCode94题二叉树的中序遍历] | 刷题打卡

总结

加油！hxdm！！！???

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情