代码随想录刷题Day48

这次博客主要是对做过的关于二叉树系列的题目进行整理和分类。

二叉树，要处理整个树，一般少不了遍历。遍历主要可以分为：递归系列、层序遍历。

如果不遍历的话，那就是处理特殊的树了，比如完全二叉树。

递归系列

基本的递归

• 基本遍历：先序、后序、中序
  • 如果使用迭代的方法，要注意节点入栈顺序和遍历顺序相反，比如，先序遍历，入栈顺序是右左中。
  • 相关的题目有：
    • 左叶子之和
      • 遍历 +左叶子判断
    • 合并二叉树
      • 同步遍历两棵树
    • BST转换为累加树
      • 本质上是右中左的遍历操作
• 翻转左右子树
  • 递归处理左右子树后，再对根节点的左右节点交换
• 对称二叉树/相同的树
  • 两棵树内侧和内侧，外侧和外侧的递归比较
• 树的最大深度
  • 也是求树高度，这可以用在判断平衡二叉树中，用个简单if-else可以解决，左右子树的最大深度+1
• 树的最小深度
  • 层序遍历到出现第一个叶子节点，这个方法会更省事些，因为后面遇到的节点都不用遍历
  • 但是如果用递归的方法，得把所有节点都遍历完才能确定哪个叶子节点深度最小
• 平衡二叉树判断
  • 主要还是会求树高，然后再递归判断树的高度差

额外栈

这个方法是指使用一个和遍历树节点同步的栈来记录其他信息，这个方法也可以使用回溯的方法来替代解决，但是回溯比较繁琐，目前主要还是优先使用这种思路。

• 二叉树的所有路径
  • 用一个和遍历树同步的字符串栈，来记录深度遍历过程中从根节点到叶子节点的发展路径
• 找树的最左下角的值
  • 这道题使用层序遍历也是可以的，如果要使用额外栈，那就是用于记录节点的深度信息
• 路径总和
  • 这种求树的路径信息，应该可以第一反应，使用额外栈的方式解决，这道题是用于记录深度遍历过程中从根节点到当前节点的路径上的节点和

构造树

构造树是一个递归的过程，确定根节点，划分出左子树和右子树的范围是重点。

• 从中序和后序遍历序列构造二叉树
  • 后序遍历结果提供根节点的信息，中序遍历结果提供左右子树范围的信息
• 最大二叉树
  • 序列最大值作为根节点，左右子树序列可以自然获得
• 从有序数组中构造二叉搜索树
  • 按照平衡的定义，可以知道根节点是序列的中间元素，左右子树序列则是中间元素两侧的序列

LCA 最近公共祖先

因为代码随想录刷题几乎都是链表的树结构，所以倍增的解法在这里难施拳脚，主要还是根据最近公共祖先的定义来解决。

• 二叉树的公共祖先（不是很熟练）：
  • 回溯时候确定祖先节点，递归的终止条件是遇到空节点或者两个孩子节点。
  • 接着看两子树中是否可以找到目标孩子节点，如果两个子树都可以找到，说明该节点是根节点，可以直接返回当前root节点了。
• 二叉搜索树LCA:
  • 可以直接依赖BST的性质了，遍历方向分叉之处就是根节点。

广度优先

层序遍历

层序遍历，是使用队列来记录一层的节点，并记住该层节点数目，每层循环上一层出队下一层入队。

这在高度计算，层的平均值，层的最大值，右视图，next指针在每一层中添加，这些题目中优先考虑使用队列层序遍历。

特殊的二叉树

完全二叉树

有道题是求完全二叉树的节点，如果要充分利用上完全二叉树的定义的话，就得借助满二叉树的概念，满二叉树作为递归结束的终止条件，满二叉树只需要根据最左路径和最右路径的深度进行比较可以得出判断结果。

二叉搜索树

• BST的验证
  • 这道题如果老实按照定义来递归验证就中招了，因为会出现右子树的左孩子节点小于根节点的情况。所以最保险的做法是使用中序遍历，查看结果是否是非递减的序列
• BST的最小绝对差
  • 中序遍历得到的序列，A节点的相邻两个节点一定是树中所有节点里距离A最近的两个节点。再求一次相邻节点的差值就好
• BST的插入操作
  • 先找到节点插入的位置（有种二分法的感觉），然后挂上去就好
• BST的删除操作
  • 删除节点分类：叶子节点、单孩子节点、双孩子节点
• BST修剪操作
  • 注意修剪区间左端时，不要忘记对右子树继续修剪，同理，修剪区间右端时不要忘记对左子树的继续修剪

感觉自己这个分类还是比较凌乱，但至少把刷过的那些题的大致类型都已经列出来了。