c> 用于记录Leetcode中二叉树相关题目的解法,首先最基本的二叉树的前序遍历,中序遍历和后序遍历,层次遍历的迭代实现方式一定需要倒背如流,注意理解转移的顺序即可,另外二叉树的题目一般都可以使用递归法来实现,但是注意递归三要素(递归函数的返回值,递归函数的终止条件,单层递归逻辑),看到一种比较好的统一遍历方式,可以参考以下,感觉总结出来通用的模板了: 统一的迭代法实现
- 添加统一迭代法代码实现
- 统一迭代法和层序遍历法实现方式: tree.cpp
常见算法题型
- 层序遍历:
- 层序遍历 基本的层序遍历,但是需要记录每一层的节点数目,注意此时需要获取到队列的长度来确定每一层的数量
- 层序遍历II 直接层序遍历得到数组并且进行反转即可,但是注意
C++中的reverse算法在反转vector<vector<T>>会反转内层数组的元素,所以这里需要在加入节点的时候首先加入右节点,之后加入左节点(但是我本地没有问题?) - 二叉树的右视图 只用在层序遍历的过程中记录最后一个遍历到的节点的值即可
- 二叉树的层平均值 一样的,注意定义
sum为double类型,或者$*0.1$ 来转换为double类型 - N叉树的层序遍历 注意不知道
Node*&怎么写,可以使用自动类型推导auto - 二叉树行中的最大值 同上
- 填充每一个节点的下一个节点注意在
C++中进行指针的赋值操作,其实指针就是存储数据的int,所以对于指针指向的变量进行改变的时候,堆区地址指向的变量就会发生改变,所以指针可以起到关联更新的作用 - 填充每一个节点的下一个节点II 和上面一个样,如果需要进行从右边到左边的连接,就可以使用首先加入右边的节点,之后加入左边的节点
- 二叉树的最大深度 注意层次遍历就是一种
bfs,所以可以利用bfs进行最小路径的寻找,这一个题目就是一个例子
- 翻转二叉树 除了利用递归的方式(注意递归的三要素),另外还可以利用迭代法,这是由于利用迭代法的时候每一次已经把所有节点都入栈了,所以只用在遍历每一个节点的时候对于每一个节点进行操作即可
- 对称二叉树 利用递归的方法,可以比较左右子树是否对称,所以需要定义一个函数用于判断两个树是否是镜像关系,强烈建议首先排除两个树中有
nullptr的情况 可以利用栈来记录层序遍历中相邻的元素并且进行比较操作 Leetcode_101.cpp - 二叉树的最大深度 可以利用层序遍历,也可以利用递归,两行代码速通
- 二叉树的最小深度 注意最小深度的概念,也就是距离根节点最近的叶子节点距离根节点的距离,可以利用递归,并且此时递归需要分情况判断,也就是需要分类讨论根节点的左右子树是否为空
- 完全二叉树的节点个数 层序遍历
- 判断平衡二叉树 首先利用前面的求解最大深度的方式求解树的高度,之后针对于每一个节点判断两边树的高度差是否超过
1即可,当然注意此时的遍历顺序应该是后序遍历,这是由于此时需要获取到左右子树的高度之后才可以进行判断,求解高度的迭代实现方式可以利用层序遍历或者利用其他遍历方式也可以,重点就是遇到叶子节点就可以回溯了,比如利用后序遍历获取最大高度: Leetcode_110.cpp - 二叉树的所有路径 由于此时需要向下获取节点的相关信息,所以应该使用前序遍历(广义的前序遍历就是首先处理中间节点的逻辑,之后处理子节点的逻辑) Leetcode_257.cpp 注意一定需要统一节点处理方式,比如首先需要把根节点加入到队列中才开始操作队列取决于递归函数的单层处理逻辑
- 二叉树的所有左叶子节点的和 首先确定遍历顺序,此时只需要取出不同的节点判断左边节点是否为叶子节点即可,随便那一种遍历方式都可以,或者也可以使用递归函数,使用递归函数的时候一定需要明确递归函数的作用,这掩才可以在递归函数中把自己当成以已知条件使用
- 树中最左下角的值使用层序遍历,遍历的过程中不断记录最左边的值即可
- 路径总和 还是回溯算法,注意此时只用利用一个全局变量来记录总和,注意回溯函数的终止条件: 当前节点为叶子节点并且全局变量的值和目标值一样,代码:Leetcode_112.cpp
- 利用中序遍历和后序遍历构造二叉树 还是递归三部曲,但是注意单层递归逻辑,首先找到后序遍历的最后一个节点作为根节点,之后在中序遍历中找到这一个节点,这一个节点左边的就是左子树,右边的就是右子树,注意规划区间即可,注意终止条件 Leetcode_106.cpp
- 最大二叉树 和上面一样的套路,形成模板
- 合并二叉树 使用递归的方法非常简单,就是只是对于一个节点进行操作,判断左子树或者右子树是否为空,利用迭代法就可以利用层序遍历的方式,把两棵树的节点压入到栈或者队列中并且进行元素的比较即可,注意形成模板: Leetcode_617.cpp
- 二叉搜索树中的搜索 如果使用递归法,就类似于二分查找,没有找到就可以找左子树,找到了就可以找右子树,如果利用迭代法就不用考虑遍历方式了,由于
BST的性质,路径已经被规划出来了,只需要按照路径走即可,另外这也是一种比较高效的搜索方式 - 验证二叉搜索树 注意二叉搜索树的特点: 左子树的的的所有节点都要大于右子树中的所有节点,所以利用递归比较困难,但是考虑到二叉搜索树的中序遍历是一个有序的序列,可以求解中序遍历之后判断中序遍历有序即可,这样利用递归函数就可以做了,利用迭代法也可以
- 二叉搜索树的最小绝对值差 还是一样求解中序遍历,求解中序遍历的过程中求解相邻两个数字的差值
- 二叉搜索树的众数 迭代法结合哈希或者利用中序遍历结合最长子序列,注意中序遍历中无论那一种操作,递归函数的核心逻辑都存在于中间节点的位置不要写到其他的位置,注意形成模板: Leetcode_501.cpp
- 二叉树的最近公共祖先节点 首先需要确定遍历顺序,这里需要首先获取到底层节点的状态反馈给上层节点,所以需要使用回溯法(也就是首先遍历底层,之后遍历上层),后序遍历就是一种回溯法,具体的方法就是利用回溯进行节点的搜索,如果遇到
root == p || root == q || root == nullptr就可以直接返回了,之后上层节点接受底层节点的状态,判断返回值是否为空(其实就是判断两边树上是否存在p或者q),如果一个返回值不是nullptr那么就可以返回这一个值,表示节点都在这一颗树上面 Leetcode_236.cpp,回溯法的遍历过程如下(注意回溯法一定需要遍历到复合要求的底层才可以返回进行逻辑处理):
- 二叉搜索树的最近公共祖先节点 首先一定需要理解二叉树回溯的本质,其实就是利用递归进行节点的搜索,所以我们做题时需要首先判断遍历方式,确定相应遍历方式之后在确定单层递归的逻辑关系,这里可以使用递归法,如果当前节点的值小于两个节点的值,就可以向右递归,如果当前节点的值大于两个节点的值,就可以向左递归,同理使用跌达法也是一样的,这是由于二叉搜索树的方向已经确定了
- 二叉搜索树中的插入操作 可以使用递归或者迭代进行操作,注意递归和迭代的本质都是对于元素进行遍历操作,在迭代中注意使用一个
pre指针记录标志位置,从而确定插入点 - 删除二叉搜索树中的节点 注意删除节点的操作,使用递归的本质就是节点的搜索,所以每一次使用递归只需要关注当前节点即可,此时注意单层递归的逻辑就是首先找到右子树最左边的节点,之后把左子树的值复制给右子树最左边的节点 Leetcode_450.cpp
- 修剪二叉搜索树 注意写递归函数的时候,明确当前递归到的节点的含义,比如这里递归函数的参数为
root就说明此时遍历到节点root,所以只用关注root的逻辑即可 ,递归法: Leetcode_669_r.cpp 迭代的逻辑与递归类似,注意当某一个节点不满足要求的时候,删除方式是把左边节点或者右边节点设置为当前节点进行删除,迭代算法: Leetcode_669.cpp - 有序数组转换为平衡二叉树 这里的递增数组,由于对于根节点左边的序列,一定是向左边偏转的一段链表,同样,对于根节点右边的需要也可以是向右边偏转的链表,所以利用递归法的时候,利用区间构造当前节点的方式就是找到开始位置和结束位置的中点,利用这一个中点左边的部分构建左子树,利用中点右边的部分构造右子树,这里迭代法利用了队列来记录递归时需要的变量: Leetcode_108_d.cpp
- 将二叉搜索树转换为累加树 首先明确遍历顺序: 反中序遍历 递归法: 明确递归法的本质就是遍历到当前节点,顺序已经有递归函数的调用顺序确定了,所以只用关注当前节点的处理逻辑即可,迭代法: 利用统一迭代法的模板即可 递归法: Leetcode_538_r.cpp
- 二叉树的直径 定义链长: 叶子节点到该节点的距离(类似于深度) , 本体可以在遍历深度的过程中不断记录最大直径即可 , 并且有
直径 = 左边链长度 + 右边链长度 + 2, 遍历过程中不断记录即可