二叉搜索树心法（合集）

AI summary

type

status

date

slug

summary

特性篇

从做算法题的角度来看 BST，二叉搜索树有一个重要的性质：BST 的中序遍历结果是有序的（升序）。

那么根据这个性质，我们来做两道算法题。

230. 二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

这个需求很常见吧，一个直接的思路就是升序排序，然后找第 k 个元素呗。BST 的中序遍历其实就是升序排序的结果，找第 k 个元素肯定不是什么难事。

直接写出代码如下：

这道题就做完了，不过呢，还是要多说几句，因为这个解法并不是最高效的解法，而是仅仅适用于这道题。

如果让你实现一个在二叉搜索树中通过排名计算对应元素的方法 select(int k)，你会怎么设计？

如果按照我们刚才说的方法，利用「BST 中序遍历就是升序排序结果」这个性质，每次寻找第 k 小的元素都要中序遍历一次，最坏的时间复杂度是 O(N)，N 是 BST 的节点个数。

要知道 BST 性质是非常牛逼的，像红黑树这种改良的自平衡 BST，增删查改都是 O(logN) 的复杂度，让你算一个第 k 小元素，时间复杂度竟然要 O(N)，有点低效了。

所以说，计算第 k 小元素，最好的算法肯定也是对数级别的复杂度，不过这个依赖于 BST 节点记录的信息有多少。

我们想一下 BST 的操作为什么这么高效？就拿搜索某一个元素来说，BST 能够在对数时间找到该元素的根本原因还是在 BST 的定义里，左子树小右子树大嘛，所以每个节点都可以通过对比自身的值判断去左子树还是右子树搜索目标值，从而避免了全树遍历，达到对数级复杂度。

那么回到这个问题，想找到第 k 小的元素，或者说找到排名为 k 的元素，如果想达到对数级复杂度，关键也在于每个节点得知道他自己排第几。

那么，如何让每一个节点知道自己的排名呢？

这就是我们之前说的，需要在二叉树节点中维护额外信息。每个节点需要记录，以自己为根的这棵二叉树有多少个节点。

伪代码如下：

体会一下这里的递归思维。

当然，size 字段需要在增删元素的时候需要被正确维护，力扣提供的 TreeNode 是没有 size 这个字段的，所以我们这道题就只能利用 BST 中序遍历的特性实现了，但是我们上面说到的优化思路是 BST 的常见操作，还是有必要理解的。

538. 把二叉搜索树转换为累加树

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

按照二叉树的通用思路，需要思考每个节点应该做什么，但是这道题上很难想到什么思路。

BST 的每个节点左小右大，这似乎是一个有用的信息，既然累加和是计算大于等于当前值的所有元素之和，那么每个节点都去计算右子树的和，不就行了吗？

这是不行的。对于一个节点来说，确实右子树都是比它大的元素，但问题是它的父节点也可能是比它大的元素呀？这个没法确定的，我们又没有触达父节点的指针，所以二叉树的通用思路在这里用不了。

此路不通，我们不妨换一个思路，还是利用 BST 的中序遍历特性。

刚才我们说了 BST 的中序遍历代码可以升序打印节点的值，那如果我想降序打印节点的值怎么办？

很简单，只要把递归顺序改一下，先遍历右子树，后遍历左子树就行了。如果在遍历的过程中维护一个外部累加变量 sum，然后把 sum 赋值给 BST 中的每一个节点，不就将 BST 转化成累加树了吗？

代码如下：

这道题就解决了，核心还是 BST 的中序遍历特性，只不过我们修改了递归顺序，降序遍历 BST 的元素值，从而契合题目累加树的要求。

简单总结下吧，BST 相关的问题，要么利用 BST 左小右大的特性提升算法效率，要么利用中序遍历的特性满足题目的要求，也就这么些事儿吧。

基操篇

我们上文介绍了 BST 的基本特性，还利用二叉搜索树「中序遍历有序」的特性来解决了几道题目，本文来实现 BST 的基础操作：判断 BST 的合法性、增、删、查。其中「删」和「判断合法性」略微复杂。

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

注意，这里是有坑的哦。按照 BST 左小右大的特性，每个节点想要判断自己是否是合法的 BST 节点，要做的事不就是比较自己和左右孩子吗？但是这个算法出现了错误，因为 BST 的每个节点应该要小于右边子树的所有节点。

问题是，对于某一个节点 root，他只能管得了自己的左右子节点，怎么把 root 的约束传递给左右子树呢？请看正确的代码：

我们通过使用辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给子树的所有节点，这也是二叉树算法的一个小技巧吧。

700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

很简单，类似二分查找思想，根据 target 和 root.val 的大小比较，就能排除一边。

代码如下：

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

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回 任意有效的结果 。

对数据结构的操作无非遍历 + 访问，遍历就是「找」，访问就是「改」。具体到这个问题，插入一个数，就是先找到插入位置，然后进行插入操作。

因为 BST 一般不会存在值重复的节点，所以我们一般不会在 BST 中插入已存在的值。下面的代码都默认不会向 BST 中插入已存在的值。

上一个问题，我们总结了 BST 中的遍历框架，就是「找」的问题。直接套框架，加上「改」的操作即可。

一旦涉及「改」，就类似二叉树的构造问题，函数要返回 TreeNode 类型，并且要对递归调用的返回值进行接收。

直接看解法代码吧，可以结合注释理解：

当然，这样的递归很容易可以转化为迭代形式，执行效率更高：

450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。

这个问题稍微复杂，跟插入操作类似，先「找」再「改」。

找到目标节点了，比方说是节点 A，如何删除这个节点，这是难点。因为删除节点的同时不能破坏 BST 的性质。有三种情况，用图片来说明。

情况 1：A 恰好是末端节点，两个子节点都为空，那么它可以当场去世了。

情况 2：A 只有一个非空子节点，那么它要让这个孩子接替自己的位置。

情况 3：A 有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。我们以第二种方式讲解。

三种情况分析完毕，填入「找」的框架，简化一下代码：

注意：这里交换节点时偷懒直接改了 val 字段。仅对于这道算法题来说是可以的，但这样操作并不完美，我们一般不会通过修改节点内部的值来交换节点。因为在实际应用中，BST 节点内部的数据域是用户自定义的，可以非常复杂，而 BST 作为数据结构（一个工具人），其操作应该和内部存储的数据域解耦，所以我们更倾向于使用指针操作来交换节点。

构造篇

上文讲了中序遍历对 BST 的重要意义，以及 BST 的基本操作。现在来循序渐进地讲两道题，如何计算所有有效 BST。

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

这就是一个正宗的穷举问题，那么什么方式能够正确地穷举有效 BST 的数量呢？

我们前文说过，不要小看「穷举」，这是一件看起来简单但是比较有技术含量的事情，问题的关键就是不能数漏，也不能数多，你咋整？

之前说过，二叉树算法的关键就在于明确根节点需要做什么，其实 BST 作为一种特殊的二叉树，核心思路也是一样的。

举个例子，比如给算法输入 n = 5，也就是说用 {1,2,3,4,5} 这些数字去构造 BST。

首先，这棵 BST 的根节点总共有几种情况？

显然有 5 种情况对吧，因为每个数字都可以作为根节点。

比如说我们固定 3 作为根节点，这个前提下能有几种不同的 BST 呢？

根据 BST 的特性，根节点的左子树都比根节点的值小，右子树的值都比根节点的值大。

所以如果固定 3 作为根节点，左子树节点就是 {1,2} 的组合，右子树就是 {4,5} 的组合。

左子树的组合数和右子树的组合数乘积就是 3 作为根节点时的 BST 个数。

我们这是说了 3 为根节点这一种特殊情况，其实其他的节点也是一样的。

那你可能会问，我们可以一眼看出 {1,2} 和 {4,5} 有几种组合，但是怎么让算法进行计算呢？

其实很简单，只需要递归就行了，我们可以写这样一个函数：

注意 base case，显然当 lo > hi 闭区间 [lo, hi] 肯定是个空区间，也就对应着空节点 null，虽然是空节点，但是也是一种情况，所以要返回 1 而不能返回 0。

这样，题目的要求已经实现了，但是时间复杂度非常高，肯定存在重叠子问题。类似动态规划，消除重叠子问题的方法，无非就是加一个备忘录：

这样，这道题就完全解决了。

那么，如果给一个进阶题目，不止让你计算有几个不同的 BST，而是要你构建出所有有效的 BST，如何实现这个算法呢？

95. 不同的二叉搜索树 II

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

明白了上道题构造有效 BST 的方法，这道题的思路也是一样的：

穷举 root 节点的所有可能。

递归构造出左右子树的所有有效 BST。

给 root 节点穷举所有左右子树的组合。

直接看代码：

注意：start > end 时需要返回 [None]，而不是 None 。

举例来说吧，什么时候会进到这个 if 语句？当你创建叶子节点的时候，对吧。那么如果你这里不加 null，直接返回空列表，那么下面的内层两个 for 循环都无法进入你的那个叶子节点就没有创建出来。

后序篇

其实二叉树的题目真的不难，无非就是前中后序遍历框架来回倒嘛，只要你把一个节点该做的事情安排好，剩下的抛给递归框架即可。

但是对于有的题目，不同的遍历顺序时间复杂度不同。尤其是这个后序位置的代码，有时候可以大幅提升算法效率。

下面就讲一个经典的算法问题，可以直观地体会到后序位置的妙用。

1373. 二叉搜索子树的最大键值和

给你一棵以 root 为根的 二叉树 ，请你返回任意二叉搜索子树的最大键值和。
二叉搜索树的定义如下：
任意节点的左子树中的键值都小于此节点的键值。
任意节点的右子树中的键值都大于此节点的键值。
任意节点的左子树和右子树都是二叉搜索树。

那有的读者可能会问，输入的是一棵普通二叉树，有没有可能其中不存在 BST？

不会的，因为按照 BST 的定义，任何一个单独的节点肯定是 BST，也就是说，再不济，二叉树最下面的叶子节点肯定都是 BST。

刚才说了，二叉树相关题目最核心的思路是明确当前节点需要做的事情是什么。

那么我们想计算子树中 BST 的最大和，站在当前节点的视角，需要做什么呢？

我肯定得知道左右子树是不是合法的 BST，如果下面的这俩儿子有一个不是 BST，以我为根的这棵树肯定不会是 BST。

如果左右子树都是合法的 BST，我得瞅瞅左右子树加上自己还是不是合法的 BST 了。因为按照 BST 的定义，当前节点的值应该大于左子树的最大值，小于右子树的最小值，否则就破坏了 BST 的性质。

因为题目要计算最大的节点之和，如果左右子树加上我自己还是一棵合法的 BST，也就是说以我为根的整棵树是一棵 BST，那我需要知道我们这棵 BST 的所有节点值之和是多少，方便和别的 BST 争个高下。

根据以上三点，站在当前节点的视角，需要知道以下具体信息：

左右子树是否是 BST。

左子树的最大值和右子树的最小值。

左右子树的节点值之和。

需要知道子树的信息，显然后序遍历更合适。又需要返回值，所以使用「分解问题」的思维模式。

定义一个 findMaxMinSum 函数做一些计算任务，返回一个大小为 4 的 int 数组，我们暂且称它为 res，其中：

res[0] 记录以 root 为根的二叉树是否是 BST，若为 1 则说明是 BST，若为 0 则说明不是 BST

res[1] 记录以 root 为根的二叉树所有节点中的最大值；

res[2] 记录以 root 为根的二叉树所有节点中的最小值；

res[3] 记录以 root 为根的二叉树所有节点值之和。

直接看代码实现吧：

这样，这道题就解决了，findMaxMinSum 函数在遍历二叉树的同时顺便完成了目标，时间复杂度只有 O(N)。