手把手带你刷二叉搜索树（第一期）

3 years ago

source link: https://labuladong.github.io/algo/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%B3%BB%E5%88%97/BST1.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

手把手带你刷二叉搜索树（第一期）

👆让天下没有难刷的算法！若 GitBook 访问太慢，可尝试 GiteePages 或 GitHubPages！

相关推荐：

读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：

230.BST第K小的元素（中等）

538.二叉搜索树转化累加树（中等）

1038.BST转累加树（中等）

前文手把手带你刷二叉树已经写了第一期，第二期和第三期，今天写一篇二叉搜索树（Binary Search Tree，后文简写 BST）相关的文章，手把手带你刷 BST。

首先，BST 的特性大家应该都很熟悉了：

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

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

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

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

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

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

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

＿＿＿＿＿＿＿＿＿＿＿＿＿

本文只能在 labuladong 公众号查看，关注后可直接搜索本站内容：