【牛客面试必刷TOP101】Day7.BM31 对称的二叉树和BM32 合并二叉树
作者简介：大家好，我是未央；
博客首页：未央.303
系列专栏：牛客面试必刷TOP101
每日一句：人的一生，可以有所作为的时机只有一次，那就是现在！！！！！
文章目录
前言
一、对称的二叉树
题目描述
解题分析
二、合并二叉树
题目描述
解题分析
总结
前言
一、对称的二叉树
题目描述
描述：
给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
例如：
下面这棵二叉树是对称的：
下面这棵二叉树不对称：
数据范围：节点数满足 0≤n≤1000，节点上的值满足∣val∣≤1000；
要求：空间复杂度 O(n)，时间复杂度O(n)
备注：
你可以用递归和迭代两种方法解决这个问题；
示例1：
示例2：
解题分析
题目的主要信息：
- 判断一棵二叉树是否是镜像，即判断二叉树是否是轴对称图形
轴对称：
非轴对称：
本题我们采用递归的方法进行解答更加简单；
解题思路：
前序遍历的时候我们采用的是“根左右”的遍历次序，如果这棵二叉树是对称的，即相应的左右节点交换位置完全没有问题，那我们是不是可以尝试“根右左”遍历，按照轴对称图像的性质，这两种次序的遍历结果应该是一样的。
不同的方式遍历两次，将结果拿出来比较看起来是一种可行的方法，但也仅仅可行，太过于麻烦。我们不如在遍历的过程就结果比较了。而遍历方式依据前序遍历可以使用递归：
- 本级任务： 每个子问题，需要按照上述思路，“根左右”走左边的时候“根右左”走右边，“根左右”走右边的时候“根右左”走左边，一起进入子问题，需要两边都是匹配才能对称。
- 终止条件： 当进入子问题的两个节点都为空，说明都到了叶子节点，且是同步的，因此结束本次子问题，返回true；有当进入子问题的两个节点只一个为空，或是元素值不相等，说明这里的对称不匹配，同样结束本次子问题，返回false。
- 返回值： 每一级将子问题是否匹配的结果往上传递。
解题步骤：
- step 1：两种方向的前序遍历，同步过程中的当前两个节点，同为空，属于对称的范畴。
- step 2：当前两个节点只有一个为空或者节点值不相等，已经不是对称的二叉树了。
- step 3：第一个节点的左子树与第二个节点的右子树同步递归对比，第一个节点的右子树与第二个节点的左子树同步递归比较。
图示过程分析：
代码编写：
二、合并二叉树
题目描述
描述：
已知两颗二叉树，将它们合并成一颗二叉树。
合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。
例如：
两颗二叉树是:
合并后的树为：
数据范围：树上节点数量满足 0≤n≤500，树上节点的值一定在32位整型范围内。
进阶：空间复杂度O(1) ，时间复杂度O(n)；
示例1：
示例2：
解题分析
题目的主要信息：
- 合并（相加）二叉树位置相同的节点；
- 缺少的节点用另一棵树来补，若都缺则返回NULL；
解题思路：
递归前序遍历
要将一棵二叉树的节点与另一棵二叉树相加合并，肯定需要遍历两棵二叉树，那我们可以考虑同步遍历两棵二叉树，这样就可以将每次遍历到的值相加在一起。遍历的方式有多种，这里推荐前序递归遍历。
解题步骤：
- step 1：首先判断t1与t2是否为空，若一个为空则用另一个代替，若都为空，返回的值也是空。
- step 2：然后依据前序遍历的特点，优先访问根节点，将两个根点的值相加创建到新树中。
- step 3：两棵树再依次同步进入左子树和右子树。
代码编写：
总结
