本文主要是介绍二叉树总结点睛，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、二叉树

1、常见名词

DFS   (depth first search )  	深度优先遍历

BFS （breadth first search ) 	广度优先遍历

BST  （binary search tree）    二叉搜索树

AVL（Adelson-Velsky and Landis）	平衡二叉搜索树

heap  堆

2、常见分类

• 满二叉树：是一种特殊的完全二叉树。只有度为0的节点和度为2的节点，且度为0的节点在同一层

  • 什么是二叉树的度：就是二叉树中 节点和 节点 的线，有 n 个节点，就有 n-1 个度
  • 深度为 k 的 满二叉树的节点数量：2^k-1

• 完全二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。

• 二叉搜索树：前面两种都是没有数值的，这个是有数值的树。且是有序树

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树
    • 即 大小顺序 就是 左 中 右

• 平衡二叉搜索树： 又被称为AVL（Adelson-Velsky and Landis）树

  • ​ 在满足二叉搜索树的前提下：

  ​ 要么是一棵空树，

  ​ 要么它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树（所谓高度，即层数）

  平衡二叉搜索树的增删操作的时间复杂度都是 logN

• 红黑树

  • 是 自平衡的二叉搜索树
  • 把树中的结点定义为红黑两种颜色，并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍。
  • set、map等数据结构都是基于红黑树实现的。

• 堆

  • 可分为最大堆和最小堆，也就是大顶堆、小顶堆。
  • 最大堆中根节点的值最大，最小堆中根节点的值最小。

• 前缀树 字典树 Trie

  • 是一颗非典型的多叉树模型，多叉好理解，即每个结点的分支数量可能为多个。
  • 力扣 第208题

3、常见应用

​ C++ 中 map、set、multimap、multiset的底层实现都是平衡二叉搜索树，所以他们的增删操作的时间复杂度都是 logN。

​ （unordered_set 和 unordered_map）的底层实现是哈希表，增删操作的时间复杂度为 1。

4、二叉树存储方式

• 链式存储 ：即用指针存储。（常用这种方式）

// 链式存储的二叉树的节点定义方式
struct TreeNode
{
    int val ;
    TreeNode* leftChild ;
    TreeNode* rightChild ;
    **// 注意初值列是用小括号幅值，而不是等于号哦！！！！**
    TreeNode (int x) : val (x) , left (NULL), right (NULL)  {}
}

• 顺序存储 ： 即用数组存储。

  相当于用 广度优先遍历 BFS，从上到下，从左到右。

  如果父节点的数组下标为 i ，则它的左孩子下标为 2 * i +1，右孩子下标为 2 * i +2。

5、二叉树的遍历（与图论中的最基本的两种遍历方式相同）

• 1、DFS depth first search 深度优先遍历：先忘深度走，遇到叶子节点再往回走。

  • 前序遍历（前中后指叶子节点）
    • 中序遍历
    • 后续遍历

• 2、BFS breadth first search 广度优先遍历：一层一层的去遍历。

  • 层次遍历

6、遍历方式的实现

栈的应用： 其实就是一种实现递归的结构，因此前中后序遍历的逻辑可以借助栈，来实现 非递归 的方式。

队列的应用： 层序遍历的实现一般是使用队列，因为队列先进先出的特点，巧好是实现层次遍历所需要的。

递归在本质上就是一种栈的结构，如果可以用栈来实现，自然而然就想到可以用递归来实现。
递归代码虽然看起来简洁，但是当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出。

因此用栈基于循环实现的代码的鲁棒性要好一些。

1、递归法

• 前序遍历：根节点，递归左子树，递归右子树，终止条件是 节点为空。
• 中序遍历：递归左子树，根节点，递归右子树，终止条件是 节点为空。
• 后序遍历：递归左子树，递归右子树，根节点，终止条件是 节点为空。

2、迭代法

• 1、前序遍历：
  *
• 2、中序遍历
  *
• 3、后序遍历
  *
• 4、层次遍历
  *

7、用迭代法遍历的代码实现，有两种

* 1）第一种迭代实现

处理前序遍历和后序遍历比较相似，也比较直观，但是中序遍历就跟这两种的思路不同，由于它遍历和访问的顺序不同导致的结果

在用迭代法遍历树的时候，其实是有两个操作

1）处理节点：即将元素放进 result 数组中，处理的过程即出栈

2）访问节点：即遍历节点，访问的过程即压栈

对于前序遍历，其顺序是 中左右，先访问的元素是中间节点，先处理的元素也是中间节点，由于访问元素和处理元素的顺序是一致的，都是中间节点，所以可以比较便捷

对于中序遍历，其顺序是左中右，先访问的是根节点，然后一层一层向下访问，直到达到树左面的最底部，在开始处理节点（也就是在把节点的数组都放进 result 数组中），这造成了处理顺序和访问顺序是不一致的。 因此在使用迭代法写中序遍历时，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

对与后序遍历，其顺序为左右中，是根据前序遍历改成的。

——>先序遍历：中左右——>调整左右顺序：中右左——>反转数组——>左右中

• 1、前序遍历：先将跟节点放入栈中，然后将右孩子加入栈，再加入左孩子。
  • 为什么要先加入 右孩子，再加入左孩子呢？
  • 因为这样出栈的时候才是中左右的顺序。
• 2、中序遍历
  • 借用指针遍历访问节点，访问的过程即压栈
  • 借用栈处理节点上的元素，处理的过程即出栈
• 3、后序遍历
  • ①先序遍历：中左右——> ②调整左右顺序：中右左——> ③反转数组——>左右中
• 4、层次遍历
  *

* 2）第二种迭代实现 / 标记法

​ 1、为什么要有标记法呢？

​ 因为第一种迭代法中，前中后 三种迭代遍历 的实现代码的风格不那么统一，中序和前后序处理的思路完全不同。

​ 2、那么怎么解决中序遍历中，访问节点和处理节点不一致的情况呢？

​ 将访问的节点放入栈中，把要处理的节点也放入栈中，但是要做标记。

​ 标记的方法就是要处理的节点放入栈之后，紧接着放入一个空指针，作为标记

​ 3、根据中序遍历，就可以用标记法统一来处理 前中后序的遍历了

下图为前序遍历：注意因为是用的栈来存储数据，因此实际压栈的顺序为 右、左、中

8、层序遍历法的实现

​ 层序遍历需要借助一个 辅助的数据结构 即队列，来实现。

​ 层序遍历方式与图论中的广度优先遍历一样，这里只是应用在二叉树上。

二、递归三部曲

递归的实现其实就是：每一次递归调用都会把 函数的局部变量、参数值、返回地址等压入栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因

0、先介绍一些技巧：

1、关于递归函数是否需要返回值呢？

​ 如果需要遍历整颗树，递归函数就不能有返回值。如果需要遍历某一条固定路线，递归函数就一定要有返回值！

​ 如果需要搜索整颗二叉树，那么递归函数就不要返回值，如果要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回。

2、栈如何来模拟回溯呢？

​ 想要实现回溯，就需要记录两个遍历，一个是节点，一个是头结点到该节点的路径数值的总合。

​ 可以用一个 pair<TreeNode*, int> 即 ： pair<节点指针，路径数值>

一个pair 为栈中的一个元素。

3、什么时候递归函数前面加if，什么时候不加if

一般情况来说：如果让空节点（空指针）进入递归，就不加if，如果不让空节点进入递归，就加if限制一下， 终止条件也会相应的调整。

关于回溯，什么情况下需要回溯呢？

​ 好像是需要，用到一个与节点对应的值时，这个一般也可理解为，递归函数的参数有两个，一个是节点，另一个是与别的对应的变量。因为这个变量是需要参与计算的，所以才需要回溯

4、二叉树题目选择什么遍历顺序？

* 涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定是前序，都是先构造中节点
* 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算
* 求二叉搜索树的属性，一定是中序，要不白瞎了有序性

对于求普通二叉树的属性问题，有时候也会用前序，比如在求深度，和找所有路径时，这样是为了方便让父节点指向子节点。所以求普通二叉树的属性还是要具体问题具体分析。

1、确定递归函数的参数和返回值

确定哪些参数是递归过程中需要处理的，那么就在递归函数里加上这个参数，

并且还要明确每次递归的返回值是什么，进而确定递归函数的返回类型

2、确定终止条件

写完递归算法在运行时，经常会遇到栈溢出的错误，就是没写终止条件，或者终止条件写的不对，

操作系统也是一个栈的结构来保存每一层递归的信息，

如果没有终止，操作系统的内存栈必然就会溢出。

3、确定单层递归的逻辑

确定每一层递归需要处理的信息，

在这里也就会重复调用自己来实现递归的过程。

4、时间复杂度的分析

递归算法的时间复杂度 = 递归的次数 * 每次递归中的操作次数

三、平衡二叉树

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

1、定义：

​ 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

​ 由图可以知道：

	* 当求高度的时候，只能从下往上去查，所以只能是**后序遍历**（ 左 右 中）
	* 当求深度的时候，可以从上到下去查，这时候是用**前序遍历**（中 左 右）。但当要求的求根节点的深度时，根节点的深度就是这棵树的最大高度，所以此时也可以用后序遍历。

2、遍历顺序

​ 后续遍历

• 递归写法：（左右中）

  • 1）明确递归函数的参数和返回值
    • 参数：仅需要传入节点指针即可。 返回值：需要一个 int 类型变量存放该节点对应树的高度
    • 为了给平衡加上标记，即表示出 节点的左右子树是否差值大于 1，
      • 方法是，当传入的节点对应的树已经不是二叉树，那么返回它的高度就没有意义了，此时返回 -1 ，来标记出不符合平衡树的规则。
      • 所以这个 int 类型变量返回值 要么是 -1 ，（表明已经不是二叉平衡树了），要么是这个节点对应的树的高度。
  • 2）明确终止条件
    • 遇到空节点，则返回 0，表示当前节点对应的树的高度为 0。
  • 3）明确单层递归的逻辑
    • 判断当前传入节点的子树是否为平衡二叉树，需要计算其左右子树的高度差。
    • 分别求出左右子树的高度，如果差值 小于等于1，则返回当前二叉树的高度，否则返回 -1，表示已经不是二叉树了。

• 迭代写法：

  • 注意在求深度时，是用层序遍历实现的
  • 求高度的时候，就不能通过层序遍历了。

  整体思路是：

  1）先定义一个函数，专门用来求高度，

  2）这个函数通过栈模拟后序遍历，来找每一个节点的高度，其实就是通过求传入节点对应子树的最大深度，将这个最大深度作为其高度。

  3）然后再用栈来模拟前序遍历，遍历每一个节点的时候，再去再去判断左右孩子的高度是否符合。

四、二叉搜索树 BST

​ 迭代法遍历：

BST 用迭代法时，不需要借助栈或队列就可实现遍历，

一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。

对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。

五、做题总结

第226题 反转二叉树

第101题 对称二叉树

第104题 二叉树的最大深度

第111题 二叉树的最小深度

第257题 二叉树的所有路径

第513题 找左下角的值

第112题 路径总和

第106题 从中序与后序遍历序列构造二叉树

第617题 合并二叉树

第700题 搜索一棵二叉树

第98题 验证二叉树

第530题 二叉搜索树的最小绝对差

第501题 二叉搜索树的众数

第236题 二叉树的最近公共祖先

第235题 二叉搜索树的公共祖先

第701题 二叉搜索树中的插入操作

第450题 删除搜素树中的节点

第669题 修剪一棵二叉搜索树

第108题 将有序数组转换为二叉搜索树

哈哈哈

第226题、递归不能用中序

​ 反转即是把每个节点的左右孩子交换一下，（左右孩子对应的子树也一起交换）

​ 代码实现：可以有9种写法

• 深度优先遍历——递归法——前序遍历、后序遍历
• 深度优先遍历——迭代法——前序遍历、中序遍历、后序遍历
  • 使用标记法时，总是忘记在中节点入栈后加上空节点入栈，咳咳咳~
• 广度优先遍历——层序遍历
  • 层序遍历还不熟悉，深度优先遍历是用栈，层序遍历是用队列，
  • 层序遍历的精髓就是定义了一个 size 来控制每次出队的元素
  • 所以在 for 循环中的逻辑顺序为：
    • 1、访问 队首元素
    • 2、删除队首元素
    • 3、根据题意对 刚刚取出的队首元素 进行处理
    • 4、先左孩子入队
    • 5、再右孩子入队 完结 ~

第101题、递归法只能后续遍历实现（左右中）

​ 只能用 后序遍历 来，因为要比较的是对称结构，即比较根节点对应的 左孩子的左右中遍历结果 和 右孩子的右左中遍历结果，这两种遍历结果是否相等。因为要通过递归函数的返回值做计算。

​ 代码实现：

• 递归法：后序遍历（其实并非标准的后续遍历啦 ~ 要明白那个过程就可）

  • 1、确定递归函数的参数和返回值

    • 因为要比较的是根节点的两个子树是否是互相翻转的关系，进而判断这个树是否为对称树，所以要比较的是两个子树，所以要传入的参数自然是左子树节点和右子树节点。

    • 返回值类型为 bool 类型

  • 2、确定终止条件

    • 要比较两个节点数值是否相同，首先要把两个节点为空的情况弄清楚，否则后面的比较数值时就会操作空指针了
      • 1）左节点为空，右节点不为空。返回false
      • 2）左节点不为空，右节点为空。返回false
      • 3）左节点和右节点都为空。返回true
      • 4）左右节点都不为空，且节点的数值不相同，return false
      • 5）左右节点都不为空，且节点的数值相同，此时才做递归，做下一层的判断

  • 3、确定递归循环的步骤

    • 注意这里的递归循环是在 2-5 这里完成的

• 迭代法：

  ​ 可以用队列、栈、数组等来实现，主要的思想都是一样的。

第104题、递归法只能后序遍历实现（左右中）

因为要通过递归函数的返回值做计算。

像这种要通过先获得左右孩子的数据，然后再得到自身的数据，这样就是采用后序遍历的逻辑

代码实现：

* 递归法：后序遍历
* 迭代法：层序遍历

​ 注意：为什么要回溯？

​ 以本题中的递归函数为例： getDepth(TreeNode* node, int depth)

回溯

即对 depth 的+1 或者 -1，的操作，为啥呢，因为无论什么情况，都需要保证，递归函数中的两个参数表示的同一层的，

而在向下一层递归的过程中，相当于 node->left （ 或 node->right ）节点向下了一层，所以 depth 当然也要向下走了一层咯。

但是因为 目前所处的位置还是在本层里，所以，还是要保证本层的 depth 是本层的， 下一层的 depth 是下一层的。

第111题、递归法只能后序遍历实现（左右中）

注意最大深度和最小深的区别是什么？

1、最小深的处理

• 正确的逻辑应该为：
  • 1）如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
  • 2）右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
  • 3）最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

2、这道题还学到了一点，如何跳出双层嵌套的循环：

​ 在第一个循环中加一个 flag 标记，

​ 然后在第二个循环中加一个判断，如果满足了某个条件需要跳出双层循环，就对这个标记赋值位K，且break，

​ 然后在第一个循环中加一个判断，当标记值为K时，就 break。

这个标记可以用 int 或 bool 都可以的。

第257题、这道题开始接触真正的回溯算法

​ 这里的递归要用前序遍历，因为这样才方便把父节点指向孩子节点，找到对应的路径。

前序遍历递归三部曲：

• 1）递归函数的参数以及返回值
  • 参数：树节点，一个用于存放路径的数组 vector<string>& result，注意这里 通过引用传递，
    • 返回值：无需返回值
• 2）确定终止条件 （ 这里第一次遇到这么长的终止逻辑代码 ）
  • 本题的终止条件不再是 if(cur == nullptr) { 终止逻辑代码 }，这样写不方便找到叶子节点
  • 找叶子节点的终止逻辑 if(cur->left == nullptr && cur->right == nullptr) { 终止逻辑代码 }
    • 这里不判断cur 为空为什么没问题？是因为下面的逻辑可以控制空节点不入栈。而且根节点会在主函数中判断是否为空。
  • 对于终止逻辑代码的分析
    • 1> vector数组方便做回溯处理，因此用vector来记录路径，注意是 vector<string>
    • 2> 需要把 原本 int 类型的path，转为 string 类型 sPath
• 3）确定单层递归逻辑
  • 因为是前序遍历，所以需要先处理 中间节点，中间节点即为要记录的路径上的节点，先放进path中。
  • 接下来是递归和回溯的过程：
    • 先做递归
      • 因为 终止条件 那里没有判断节点是否为空，因此在递归这里需要加上判断，注意是对其左右孩子分别判断
      • 如果为空，则不进行下一层的递归。
      • 如果不为空，则对（左孩子）或（右孩子）进行递归。所以这儿是两个 for 循环。
    • 再做回溯
      • 首先清楚一点，回溯和递归是一一对应的关系，有一个递归，就要有一个回溯，递归和回溯不能被括号隔开，他们两个要永远用于在一起，所以回溯要紧跟着递归，不离不弃 ~

第513题 层序遍历很简单，但是偏要用一下递归法

主要介绍递归法：

​ 本题要求 最后一行 的 最左边的值

​ 所以是要沿着两个方向，

* 一个是自上而下找深度，最终的结果必须是深度最大的，对应的就是最后一行
* 一个是自左向右，要记录最左边的叶子节点的值

第112题

第一个出彩的地方

​ 求和 不用减法，而是做加法，用待求的值，依次减去路径上的值，如果最后得到的是 0，就返回 true，否则返回 false

递归的实现代码：

​ 本题使用 前 中 后 序的递归都可，因为中节点没有处理逻辑

需要遍历树的所有路径

三部曲来一遍：

• 1、确定递归函数的参数和返回值类型
  • 参数：一个根节点，一个计数器（用来统计二叉树的一条边之和是否正好是目标和）
    • 返回值类型： 本题是搜索其中一条符合条件的路径，递归函数就需要返回值，因此将返回值类型设置为 bool
• 2、确定终止条件
  • 遇到了叶子节点且count 为0 就返回 true
    • 遇到叶子节点 返回 false
• 3、单层递归逻辑
  • 递归，也就是针对非叶子节点来看，所以这里要对 递归后返回的值 进行判断和处理

这里关于回溯写一下自己的想法：因为传入的参数 有节点 和一个int 类型变量，因此在处 理递归逻辑的时候，需要对节点进行处理，因为要进下一层，而处理完，还需要回溯到本层，这样才能保证本函数的节点和本函数的值的正确的对应关系，回溯就相当于撤销了递 归处理节点的过程而已。

通常可以分开来写，或者直接写。

第二个出彩的地方：

如果是用栈来实现呢？

栈如何来模拟回溯呢？ 想要实现回溯，就需要记录两个遍历，一个是节点，一个是头结点到该节点的路径数值的总合。

可以用一个 pair<TreeNode*, int> 即 ： pair<节点指针，路径数值>

一个pair 为栈中的一个元素。

第106题

构造一棵二叉树可以分为如下六步：

* 第一步：如果数组大小为0的话，说明是空节点
* 第二步：如果不为空，那么取后序数组最后一个元素 k 作为节点元素
* 第三步：找到 k 在中序数组的位置，作为切割点
* 第四步：切割中序数组，切成中序左数组和中序右数组 （注意这里的顺序不要反了，一定是先切中序数组）
* 第五步：然后将后序数组切成后序左数组和后序右数组
* 第六步：递归处理左区间和右区间

第617题

这个题，让我明白了一个点，就是 1、2、3 这三个地方的返回值分别代表的不同的含义

1 和 2 是为了在遇到叶子节点时 ，返回上一层

3 是在遍历完整棵树之后才会进行的操作，返回

第700题

涉及到二叉搜索树就用中序遍历

两种解法都类似中序遍历：

​ 递归法

​ 迭代法

第98题

同样也是类似于中序遍历的三种解法：

​ 递归把树压入一个数组，然后再进行判断

​ 边递归边判断

​ 迭代法

注意：

​ 二叉搜索树 BST 的两个陷阱，

​ 1）不能单纯只比较 左节点小于中间节点，右节点大于中间节点，而是要比较 左子树所有节点小于中间节点，右子树所有节点大于中间节点

​ 2）关于最小节点的定义，样例中的最小节点可能是 int 的最小值，如果是这样的话，那自定义最小的 int 来进行比较时就不对了。可以不去定义这个最小变量，用最左边节点的数值进行比较，之后每一次也都要进行更新。

第501题

什么是众数？

​ 在一组数中，出现次数最多的数

什么是中位数？

​ 按顺序排列的一组数据中，位于中间位置的数

法一：普通二叉树通用递归方法：：

1、首先在方法一中学到的第一个要点：

如果要搜索的是普通二叉树，而不是本题说明的二叉搜索树BST，对于常规解法，需要对pair进行排序，这时候有一个第一次用到的sort用法

// vec 是一个存储了pair类型的数组，现在需要按照pair的second值来对vec进行排序
// 所以定义了 cmp 函数，在 cmp 函数中定义了排序的规则，

vector<pair<int, int>> vec;
bool static cmp (const pair<int, int>& a, const pair<int, int>& b)
{
	// 返回 a > b ，则为降序排列，即最大值在前
	return a.second > b.second;
	
	// 返回 a < b ，则为升序排列，即最小值在前	即： return a.second 《 b.second;
}

sort(vec.begin(), vec.end(), cmp);	// 前两个参数表示排序的范围，cmp来确定排序的方式

总结：通用法思路比较直接，主要就是最后怎么对频率进行排序这点需要注意。

法二：BST递归法

2、因为二叉搜索树是有大小顺序的，那么就比较相邻元素即可统计出现的频率

3、既然是要比较相邻两个节点，那么此时就需要定义一个 指向前一个节点的指针pre 用来存储前一个节点，和一个 指向当前节点的指针cur 用来存储当前节点，注意在定义指针时，为了避免野指针，要将其初始化为空指针哦~，这样当判断出 pre == nullptr 时，我们就知道比较的是第一个元素。

4、本题中要求的是最大频率的元素的集合，那么就有可能不止一个元素是最大频次，这时候有两种处理方式，

​ 第一种先遍历一遍数组，找出最大频率，然后再重新遍历一遍数组，把出现频率最大的元素放进集合

​ 第二种是更可取的，就是多定义一个变量maxCount，用来更新最大频率，把频率等于maxCount的元素放进结果集合中，但是当出现比maxCount更大的频率时，就更新结果集合，将其情况，并更新maxCount。这样只遍历一次就能达到效果。

5、关于比较

​ 这里涉及到两处比较：

​ 一个是pre节点与cur节点的比较，分了三种情况来处理

​ 一个是频率的比较，没有使用map容器来计数，而是定义一个 int 类型的变量来计数，对频率值进行更新

法三：迭代法

与法二基本类似，同样是采用中序遍历

第236题

思路：

找公共祖先，那得自底向上查找。

怎么自底向上查找呢？回溯呀，回溯的过程就是从底向上。

后序遍历就是天然的回溯的过程，他最先处理的一定是叶子节点。注意：二叉树只能通过后序遍历（即：回溯）实现自底向上的遍历方式。

那么如何判断一个节点是节点q和节点p的公共祖先呢？

​ 如果找到一个节点，发现左子树出现节点p，右子树出现节点q，或者是左子树出现节点q，右子树出现节点p，那么这个节点就是他们的最近公共祖先。

总结：

使用后序遍历，回溯的过程就是自底向上遍历节点，一旦发现满足这个条件的节点，就是最近的公共祖先节点了。

理解一：

1. 如果你能在当前这棵树上找到p和q的公共节点，那就返回这个公共节点
2. 如果没有找到公共节点但是找到了p或者q它们自己，那你就返回找到的那个p或者q
3. 再否则你啥也没找到，就返回null，而不是单纯的返回公共节点。

理解二：

1. 先看root，如果root先占了一个值，那直接返回root，否则就看left, right

2. 只要left, right任意一个是么有的，那就返回有的那个

3. 因为么有的那个下面肯定没有目标值，有的那个肯定是找到了目标值才返回来的，无论多深，返回上去的时候那个left, right都是返回那个目标值

4. 如果在两个值不在同一层，那么就是第一步了，如果在同一层，那就是它上面的那个值，所以逻辑是写在left, right里面实现的。

第235题

与上一题不同的是 这是一颗BST，可以有效地利用 BST 树的性质

BST是有序的，在从上到下遍历的过程中，当前节点的值在 【q, p】的区间里，则说明该节点就是最近的公共祖先，

普通二叉树需要利用回溯，由底向下查找，后续递归遍历

BST 只需要从上向下遍历即可，这里 前中后序遍历 都是可以的。这里并没有处理中间节点的逻辑，因此遍历顺序也就无所谓了

BST 用迭代法时，不需要借助栈或队列就可实现遍历，

一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。

对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。

第701题

​ 1、递归返回值直接返回节点

​ 2、不用递归返回值，而是定义一个节点用来临时存储前一个节点

第450题

注意：删除比插入思路更难

单层递归逻辑：

共有 5 种情况：

• 1）没找到需要删除的节点，遍历到空节点直接返回
• 2）找到了删除的节点，左右孩子都为空，直接删除节点，返回nullptr为根节点
• 3）找到了删除的节点，删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
• 4）找到了删除的节点，删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
• 5）找到了删除的节点，左右孩子都不为空，则将删除节点的左子树节点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

第669题

修剪问题其实就是从二叉树中删除节点的问题，

递归三部曲：

• 1）确定递归函数的参数以及返回值类型

本题是需要遍历整棵树，通常在遍历整棵树的时候，我们不设返回值，

本题在确定递归函数的返回值时，可以有返回值，也可以没有返回值，但是没有返回值的处理会比较麻烦。因此设定本题用函数的返回值

有返回值的话，我们可以通过递归函数的返回值来移除节点

• 2）确定终止条件

本题的修剪操作不是在终止条件是进行的，所以终止条件就是简单地遇到空节点就返回

• 3）确定单层递归逻辑
  • 1> 如果当前节点元素小于 low 的数值，那么应该递归右子树，并返回右子树符合条件的头结点。
  • 2> 如果当前节点的元素大于 high 的数值，那么应该递归左子树，并返回左子树符合条件的头结点
  • 3> 接下来要将下一层处理完左子树的结果赋给 root->left ，处理完右子树的结果赋值给 root->right ，最后返回 root 节点。

对于单层递归逻辑这里，前两步和第三步的关系，刚开始真的很难想，其实现在可能也没有搞明白，
其实前两步就相当于把root变为符合 [low , high]这个区间的一个节点了
第三步是相当于对root的左右子树的修剪

这里包含了两层关系，
第一层是判断根节点是否符合，也就是 单层递归逻辑中的前两步
第二层是判断根结点的 左右子树 是否符合，也就是 单层递归逻辑中的第三步

发现自己想递归过程的时候，总是莫名其妙的会混淆，常常是因为 当前节点是什么搞混了，要明白当前的节点是随着递归的过程在改变，尤其是有递归函数的返回值时，更应该注意一下，return 给了谁，谁又是当前的节点，这样才能搞明白这个逻辑，要不然就是一头雾水的

一位录友很棒的理解：

1、当前节点看做根节点

2、判断当前节点是否在指定的区间内

3、如果小于左区间，说明当前节点的左子树需要被剪掉，就以当前节点的右孩子为根节点继续去找，返回给上一层进行连接（返回值一定是右子树中的某个节点，相当于把左子树剪掉了）

4、如果大于右区间，说明当前节点的右子树需要被剪掉，就以当前节点的左孩子为根节点继续去找，返回给上一层进行连接（返回值一定是左子树中的某个节点，相当于把右子树剪掉了）

5、如果在区间内，就既要找当前节点的左孩子，又要去找当前节点的右孩子，分别将找到的节点对当前节点的左孩子和根节点的右孩子进行更新。

第108题

1、转换为一棵高度平衡的二叉搜索树 与 转换为一棵普通二叉搜索树 有什么区别呢？

​ 其实 不用强调平衡，也会是平衡，因为用数组来构造二叉树，构成平衡是自然而然的事儿。

​ 因为大家都默认从数组中间位置取值作为节点元素，一般不会随机取

2、构造二叉树的精髓就是找寻分割点，

​ 分割点作为当前节点，然后递归左区间和右区间

这篇关于二叉树总结点睛的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！