二叉树

  1. 理论基础
    1. 二叉树的种类（主要）：满二叉树、完全二叉树
    2. 二叉树的存储方式：链式存储（指针）和顺序存储（数组，父节点i，左节点i×2+1，右节点i×2+2）
    3. 二叉树的遍历方式
      1. 深度优先遍历：前序中序后序遍历（规定中间节点的顺序）
      2. 广度优先遍历
  2. 二叉树的递归遍历
    1. 递归算法的三个要素
      1. 确定递归函数的参数和返回值
      2. 确定终止条件
      3. 确定单层递归的逻辑
  3. 二叉树的迭代遍历

    1. 前序遍历：用栈去实现。合理安排进栈出栈的时机，栈内存的是一个完整的节点，所以可以直接把这个节点拿出来继续做操作。

    2. 中序遍历：用栈去实现，但是，在中序遍历中，访问顺序和处理顺序是不同的，所以需要先用指针遍历，然后再用栈处理。

    3. 后序遍历：同前序遍历。但是思路上是，中右左->反转->中左右，如果是想仿照递归法的思路，仅仅调整result.add和dq.push()的顺序会进入死循环。

  4. 二叉树的层序遍历

    1. 迭代法：利用队列，按序进，按序出。需注意设计如何按层加入结果。利用上次队列的长度控制。

    2. 递归法：先到达最后一层左节点处，确定每一层的第一个节点，以及树的层数，然后递归到每一层的右节点，再确定。

      1. 关键参数：deep

    3. 相关题目

      1. 二叉树的层序遍历II：同二叉树的层序遍历思路

        1. 最后反转List（直接用函数reverse，或者用一个for循环）

        2. 利用链表收集答案，将新得到的答案插入到头部

      2. 二叉树的右视图

        1. 同二叉树的层序遍历思路
          1. 最后收集每一层的最后一个答案

      3. 二叉树的层平均值

        1. 同二叉树的层序遍历思路

          1. 最后计算sum值和average

          2. 注意double & int

      4. N叉树的层序遍历

        1. 同二叉树的层序遍历思路
          1. 最后加入队列的时候遍历孩子List

      5. 在每个树行中找最大值

        1. 同二叉树的层序遍历思路

          1. 优化，在每层队列的数值中定位到最大值：max = Math.max(max, node.val);
          2. 不用，都存进tempList之后再sort了

        2. 剪枝操作时，可以不用初始化一个List

          1
          2
          3
          if(root == null){
                      return Collections.emptyList();
                  }

      6. 填充每个节点的下一个右侧节点

        1. 同层序遍历思路
          1. 但是要注意维护两个节点，一个是poll出来的当前节点，还有一个当前节点的前一个节点。

      7. 填充每个节点的下一个右侧节点II

        1. 同上。

      8. 二叉树的最大深度

        1. 同层序遍历思路
          1. 只需记录深度

      9. 二叉树的最小深度

        1. 同层序遍历思路
          1. 当左右节点皆为空时，是最小深度
          2. 因为是层序遍历，所以肯定是最小的。
  5. 翻转二叉树

    1. 明确思路：想要达成翻转二叉树的效果，只需要交换一下每个节点的左右孩子就可以。

    2. 递归法-DFS

      1. 前序遍历、后序遍历都OK

      2. 但是中序遍历不行，会将一个节点做两次交换操作（无效），递归后交换，然后又递归

    3. 迭代法-DFS

    4. 迭代法-BFS

  6. 对称二叉树

    1. 明确思路：同时遍历两颗子树，判断两颗子树的内侧元素和外侧元素是否一致。注意，只有两侧元素一致，才有继续往下判断的价值

    2. 递归法

    3. 迭代法-使用普通队列，控制入队顺序

      1. 注意LinkedList和ArrayDeque关于null的设定
  7. 二叉树的最大深度
    1. 迭代法（同上文层序遍历思路）
    2. 递归法
  8. 二叉树的最小深度
    1. 迭代法（同上文层序遍历思路）
    2. 递归法
  9. 完全二叉树的节点个数

    1. 迭代法（同上文层序遍历思路）

    2. 递归法：后序遍历

  10. 平衡二叉树
    1. 递归法：注意什么时候返回0，什么时候返回-1
  11. 二叉树的所有路径

    1. 递归法

      1. 递归法1：在递归的过程中就拼接字符串，只携带node 和 String 参数。

      2. 递归法2：在递归的过程中只记录节点值路径，最后拼接，所以需要递归的时候需要回溯

    2. 迭代法

  12. 左叶子之和

    1. 递归法：注意确定什么是左叶子，确定怎么处理这个左叶子

    2. 迭代法

  13. 找树左下角的值

    1. 递归法：明确这个值就是深度最大的叶子结点。有全局变量：最大深度+当前叶子结点数值；遇到叶子结点时更新，但是要注意深度问题的回溯。

    2. 迭代法：太简单辣，只需要记录最后一行的第一个节点就OK。

  14. 路径总和
    1. 递归法：确定有没有返回值，这里是需要返回值的，因为我们不需要把所有的都走一遍。
  15. 从中序遍历和后序遍历中构建二叉树
    1. 递归法：递归处理左中序区间，左后序区间和右中序区间和右后序区间
      1. 这个区间每次都要构造新的数组？–>太过繁琐，不需要每次构造新数组，但是需要添加区间边界参数，引发区间开闭问题，一定要确定好这个区间开闭。
      2. 需要通过后序数组的最后一个元素确定切割位置 –>即需要通过数值找位置 –> 运用map
      3. 重点确定后序数组如何被切割？–> 先确定中序切割后的左区间元素个数，然后根据这个个数确定后序数组切割后的左区间元素个数
  16. 最大二叉树
    1. 同构建二叉树思路，注意这个时候就不需要构造一个map来找下标了，因为在求最大值的时候可以顺便获得最大值的下标。
  17. 合并二叉树
    1. 同构建二叉树思路，虽然通过但是执行用时很长，优化，可以不用从头开始构建，直接用其中一棵树构建。
    2. 优化：区分节点，节点并不是不能更改的。
  18. 二叉搜索树中的搜索
    1. 二叉搜索树：有序树
      1. 若左子树不为空，那么左子树上的所有节点的值都小于根节点的值
      2. 若右子树不为空，那么右子树上的所有节点的值都大于根节点的值
      3. 左右子树也是二叉搜索树
    2. 递归遍历时，可以根据目标值和该节点的值确定下一步只遍历一边的子树
      1. 这个是要有返回结果的，注意什么时候返回什么值
  19. 验证二叉搜索树
    1. 思路1：在递归中比较（时时刻刻规范遍历顺序、、）
      1. 问题是，如何保证该节点不仅满足与该节点的父节点的大小关系，还满足与父节点的父节点的比较关系？—-> 子子孙孙无穷尽也，nono 不能这么整
      2. 易知，二叉搜索树中序遍历得到的值构成的序列一定是升序的，所以，可以在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历得到的节点的值，如果均大于（当前节点的值大于之前中序遍历的最大值，即上一个节点），则说明整个序列是升序的。
    2. 思路2（执行用时分布和消耗内存分布都很难看、、）：用递归中序遍历将二叉搜索树转变成一个数组，比较数组是否有序
    3. 思路3：迭代法（也是中序遍历思路） —-> 前一个节点
  20. 二叉搜索树中的最小绝对差
    1. 对于二叉搜索树而言，这个最小绝对差，就是两个相邻节点之间的比较。
    2. 递归法，什么时候需要参数，什么时候不要参数？怎么处理第一个节点？
  21. 二叉搜索树中的众数
    1. 递归法：确定好到底什么时候更新？会不会有漏掉的情况？
  22. 二叉树的最近公共祖先

    1. 什么情况下，可以认定这个二叉树的最近公共祖先？

      1. 当左子树和右子树同时命中时，该节点就是两个目标节点的最近公共祖先。

      2. 节点和该节点的子树中，包含两个目标节点。

    2. 确定处理顺序，需要通过左子树返回的值和右子树返回的值来进一步处理，所以应该用后序遍历。

  23. 二叉搜索树的最近公共祖先

    1. 利用二叉搜索树有序的特点，把判断最近公共祖先，转化为判断数值与区间的问题。

    2. 递归：三种情况怎么处理。

  24. 二叉搜索树中的插入操作

    1. 根据值的大小，决定下一步递归哪一棵树。

    2. 中序遍历，遇到null就插入。

    3. 注意处理父节点，建立与父节点的关系。

  25. 删除二叉搜索树中的节点
    1. 五种删除过程中会遇到的情况

      1. 找不到被删除的节点，返回null

      2. 找到被删除的节点

        1. 是叶子节点，返回null作为新的根节点

        2. 该节点只有左孩子，左孩子作为新的根节点，返回左孩子

        3. 该节点只有右孩子，右孩子作为新的根节点，返回右孩子

        4. 该节点有右孩子也有左孩子，把右孩子作为新的根节点返回，同时，左子树需要整体插入到右子树最左边的节点下，作为其左孩子。

  26. 修剪二叉搜索树
    1. 分析情况，找到不在范围内的节点

      1. 该节点的值在边界左边，则需考虑其右子树是否在边界内。

      2. 该节点的值在边界右边，则需考虑其左子树是否在边界内。

  27. 将有序数组转换为二叉搜索树

    1. 取中间节点、累加

    2. 注意中间下标的获取，同二分查找的mid = left + (right-left)/2

  28. 把二叉搜索树转换为累加树
    1. 右中左遍历，反中序递加
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本站由 Xylumina 使用 Stellar 1.30.0 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

本"页面"访问 次 | 总访问 次 | 总访客 人