益阳网站建设企业,软件项目管理第二版课后答案,服务商标有哪些,wordpress免登陆发布接口作者简介#xff1a;大家好#xff0c;我是未央#xff1b; 博客首页#xff1a;未央.303 系列专栏#xff1a;牛客面试必刷TOP101 每日一句#xff1a;人的一生#xff0c;可以有所作为的时机只有一次#xff0c;那就是现在#xff01;#xff01;#xff01;… 作者简介大家好我是未央 博客首页未央.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两棵树再依次同步进入左子树和右子树。 代码编写 总结
