二叉搜索树心法（特性篇）

labuladong原创约 2405 字

本文讲解的例题

LeetCode	力扣	难度
1038. Binary Search Tree to Greater Sum Tree	1038. 从二叉搜索树到更大和树	🟠
538. Convert BST to Greater Tree	538. 把二叉搜索树转换为累加树	🟠
230. Kth Smallest Element in a BST	230. 二叉搜索树中第K小的元素	🟠

前置知识

阅读本文前，你需要先学习：

前文手把手带你刷二叉树已经写了思维篇，构造篇，后序篇和序列化篇。

今天开启二叉搜索树（Binary Search Tree，后文简写 BST）的系列文章，手把手带你刷 BST。

首先，BST 的特性大家应该都很熟悉了（详见基础知识章节的二叉树基础）：

1、对于 BST 的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 的值大。

2、对于 BST 的每一个节点 node，它的左侧子树和右侧子树都是 BST。

二叉搜索树并不算复杂，但我觉得它可以算是数据结构领域的半壁江山，直接基于 BST 的数据结构有 AVL 树，红黑树等等，拥有了自平衡性质，可以提供 logN 级别的增删查改效率；还有 B+ 树，线段树等结构都是基于 BST 的思想来设计的。

从做算法题的角度来看 BST，除了它的定义，还有一个重要的性质：BST 的中序遍历结果是有序的（升序）。

也就是说，如果输入一棵 BST，以下代码可以将 BST 中每个节点的值升序打印出来：

java 🟢

void traverse(TreeNode root) {
    if (root == null) return;
    traverse(root.left);
    // 中序遍历代码位置
    print(root.val);
    traverse(root.right);
}

cpp 🤖

void traverse(TreeNode* root) {
    if (root == nullptr) {
       return;
    }
    traverse(root->left);
    // 中序遍历代码位置
    print(root->val);
    traverse(root->right);
}

python 🤖

def traverse(root):
    if not root:
        return
    traverse(root.left)
    # 中序遍历代码位置
    print(root.val)
    traverse(root.right)

go 🤖

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.left)
    // 中序遍历代码位置
    fmt.Println(root.val)
    traverse(root.right)
}

javascript 🤖

var traverse = function(root) {
  if (root === null) return;
  traverse(root.left);
  // 中序遍历代码位置
  console.log(root.val);
  traverse(root.right);
};

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

寻找第 K 小的元素

这是力扣第 230 题「二叉搜索树中第 K 小的元素」，看下题目：

230. 二叉搜索树中第K小的元素 | 力扣 | LeetCode |

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

树中的节点数为 n 。
1 <= k <= n <= 10⁴
0 <= Node.val <= 10⁴

进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

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

按照这个思路，可以直接写出代码：

java 🟢

class Solution {
    int kthSmallest(TreeNode root, int k) {
        // 利用 BST 的中序遍历特性
        traverse(root, k);
        return res;
    }

    // 记录结果
    int res = 0;
    // 记录当前元素的排名
    int rank = 0;
    void traverse(TreeNode root, int k) {
        if (root == null) {
            return;
        }
        traverse(root.left, k);

        // 中序代码位置
        rank++;
        if (k == rank) {
            // 找到第 k 小的元素
            res = root.val;
            return;
        }

        traverse(root.right, k);
    }
}

cpp 🤖

class Solution {
private:
    // 记录结果
    int res = 0;
    // 记录当前元素的排名
    int rank = 0;
    void traverse(TreeNode* root, int k) {
        if (root == nullptr) {
            return;
        }
        traverse(root->left, k);

        // 中序代码位置
        rank++;
        if (k == rank) {
            // 找到第 k 小的元素
            res = root->val;
            return;
        }

        traverse(root->right, k);
    }

public:
    int kthSmallest(TreeNode* root, int k) {
        // 利用 BST 的中序遍历特性
        traverse(root, k);
        return res;
    }
};

python 🤖

class Solution:
    def __init__(self):
        # 记录结果
        self.res = 0
        # 记录当前元素的排名
        self.rank = 0

    def kthSmallest(self, root: TreeNode, k: int) -> int:
        # 利用 BST 的中序遍历特性
        self.traverse(root, k)
        return self.res

    def traverse(self, root, k):
        if not root:
            return
        self.traverse(root.left, k)

        # 中序代码位置
        self.rank += 1
        if k == self.rank:
            # 找到第 k 小的元素
            self.res = root.val
            return

        self.traverse(root.right, k)

go 🤖

func kthSmallest(root *TreeNode, k int) int {
    // 记录结果
    res := 0
    // 记录当前元素的排名
    rank := 0
    var traverse func(root *TreeNode)

    traverse = func(root *TreeNode) {
        if root == nil {
            return
        }
        traverse(root.Left)

        // 中序代码位置
        rank++
        if k == rank {
            // 找到第 k 小的元素
            res = root.Val
            return
        }

        traverse(root.Right)
    }

    // 利用 BST 的中序遍历特性
    traverse(root)
    return res
}

javascript 🤖

var kthSmallest = function(root, k) {
    // 记录结果
    let res = 0;
    // 记录当前元素的排名
    let rank = 0;
    var traverse = function(root) {
        if (root === null) {
            return;
        }
        traverse(root.left);

        // 中序代码位置
        rank++;
        if (k === rank) {
            // 找到第 k 小的元素
            res = root.val;
            return;
        }

        traverse(root.right);
    }

    // 利用 BST 的中序遍历特性
    traverse(root);
    return res;
}

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

我们后文高效计算数据流的中位数中就提过今天的这个问题：

相关信息

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

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

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

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

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

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

比如说你让我查找排名为 k 的元素，当前节点知道自己排名第 m，那么我可以比较 m 和 k 的大小：

1、如果 m == k，显然就是找到了第 k 个元素，返回当前节点就行了。

2、如果 k < m，那说明排名第 k 的元素在左子树，所以可以去左子树搜索第 k 个元素。

3、如果 k > m，那说明排名第 k 的元素在右子树，所以可以去右子树搜索第 k - m - 1 个元素。

这样就可以将时间复杂度降到 $O(logN)$ 了。

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

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

也就是说，我们 TreeNode 中的字段应该如下：

java 🟢

class TreeNode {
    int val;
    // 以该节点为根的树的节点总数
    int size;
    TreeNode left;
    TreeNode right;
}

cpp 🤖

class TreeNode {
public:
    int val;
    // 以该节点为根的树的节点总数
    int size;
    TreeNode* left;
    TreeNode* right;
};

python 🤖

class TreeNode:
    def __init__(self):
        self.val = None
        # 以该节点为根的树的节点总数
        self.size = None
        self.left = None
        self.right = None

go 🤖

type TreeNode struct {
    Val   int
    // 以该节点为根的树的节点总数
    Size  int
    Left  *TreeNode
    Right *TreeNode
}

javascript 🤖

function TreeNode() {
    var val;
    // 以该节点为根的树的节点总数
    var size;
    var left;
    var right;
}

有了 size 字段，外加 BST 节点左小右大的性质，对于每个节点 node 就可以通过 node.left 推导出 node 的排名，从而做到我们刚才说到的对数级算法。

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

BST 转化累加树

力扣第 538 题和 1038 题都是这道题，完全一样，你可以把它们一块做掉。看下题目：

538. 把二叉搜索树转换为累加树 | 力扣 | LeetCode |

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

树中的节点数介于 0 和 10⁴之间。
每个节点的值介于 -10⁴ 和 10⁴ 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。

题目应该不难理解，比如图中的节点 5，转化成累加树的话，比 5 大的节点有 6，7，8，加上 5 本身，所以累加树上这个节点的值应该是 5+6+7+8=26。

我们需要把 BST 转化成累加树，函数签名如下：

java 🟢

TreeNode convertBST(TreeNode root)

cpp 🤖

TreeNode* convertBST(TreeNode* root);

python 🤖

def convertBST(root: TreeNode) -> TreeNode:

go 🤖

func convertBST(root *TreeNode) *TreeNode {}

javascript 🤖

var convertBST = function(root) {}

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

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

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

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

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

很简单，只要把递归顺序改一下，先遍历右子树，后遍历左子树就行了：

java 🟢

void traverse(TreeNode root) {
    if (root == null) return;
    // 先递归遍历右子树
    traverse(root.right);
    // 中序遍历代码位置
    print(root.val);
    // 后递归遍历左子树
    traverse(root.left);
}

cpp 🤖

void traverse(TreeNode* root) {
    if (root == nullptr) return;
    // 先递归遍历右子树
    traverse(root->right);
    // 中序遍历代码位置
    print(root->val);
    // 后递归遍历左子树
    traverse(root->left);
}

python 🤖

def traverse(root):
    if root is None:
        return
    # 先递归遍历右子树
    traverse(root.right)
    # 中序遍历代码位置
    print(root.val)
    # 后递归遍历左子树
    traverse(root.left)

go 🤖

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // 先递归遍历右子树
    traverse(root.Right)
    // 中序遍历代码位置
    fmt.Println(root.Val)
    // 后递归遍历左子树
    traverse(root.Left)
}

javascript 🤖

var traverse = function(root) {
    if (root == null) return;
    // 先递归遍历右子树
    traverse(root.right);
    // 中序遍历代码位置
    console.log(root.val);
    // 后递归遍历左子树
    traverse(root.left);
}

这段代码可以降序打印 BST 节点的值，如果维护一个外部累加变量 sum，然后把 sum 赋值给 BST 中的每一个节点，不就将 BST 转化成累加树了吗？

看下代码就明白了：

java 🟢

class Solution {
    TreeNode convertBST(TreeNode root) {
        traverse(root);
        return root;
    }

    // 记录累加和
    int sum = 0;
    void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(root.right);
        // 维护累加和
        sum += root.val;
        // 将 BST 转化成累加树
        root.val = sum;
        traverse(root.left);
    }
}

cpp 🤖

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        traverse(root);
        return root;
    }

private:
    // 记录累加和
    int sum = 0;
    void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        traverse(root->right);
        // 维护累加和
        sum += root->val;
        // 将 BST 转化成累加树
        root->val = sum;
        traverse(root->left);
    }
};

python 🤖

class Solution:
        def __init__(self):
            # 记录累加和
            self.sum = 0
            
        def convertBST(self, root):
            self.traverse(root)
            return root

        def traverse(self, root):
            if root is None:
                return
            self.traverse(root.right)
            # 维护累加和
            self.sum += root.val
            # 将 BST 转化成累加树
            root.val = self.sum
            self.traverse(root.left)

go 🤖

func convertBST(root *TreeNode) *TreeNode {
    // 记录累加和
    sum := 0
    // define a closure for traverse
	traverse := func(root *TreeNode) {}
	traverse = func(root *TreeNode) {
		if root == nil {
			return
		}
		traverse(root.Right)
		// 维护累加和
		sum += root.Val
		// 将 BST 转化成累加树
		root.Val = sum
		traverse(root.Left)
	}
    traverse(root)
    return root
}

javascript 🤖

var convertBST = function(root){
    var sum = 0;

    var traverse = function(root) {
        if (root == null) {
            return;
        }
        traverse(root.right);
        // 维护累加和
        sum += root.val;
        // 将 BST 转化成累加树
        root.val = sum;
        traverse(root.left);
    } 

    traverse(root);
    return root;
}

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

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

本文就到这里，更多经典的二叉树习题以及递归思维的训练，请参见二叉树章节中的习题部分

引用本文的题目

安装我的 Chrome 刷题插件点开下列题目可直接查看解题思路：

LeetCode	力扣	难度
-	剑指 Offer II 054. 所有大于等于节点的值之和	🟠

二叉搜索树心法（特性篇）

1038. 从二叉搜索树到更大和树 https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree

1038. Binary Search Tree to Greater Sum Tree https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree

230. 二叉搜索树中第 K 小的元素 https://leetcode.cn/problems/kth-smallest-element-in-a-bst

230. Kth Smallest Element in a BST https://leetcode.com/problems/kth-smallest-element-in-a-bst

538. 把二叉搜索树转换为累加树 https://leetcode.cn/problems/convert-bst-to-greater-tree

538. Convert BST to Greater Tree https://leetcode.com/problems/convert-bst-to-greater-tree

寻找第 K 小的元素

BST 转化累加树