手把手带你刷二叉搜索树(第一期)

GitHub undefined undefined undefined

培养框架思维,真正爱上算法!关注公众号查看更新文章👆

相关推荐:

读完本文,你不仅学会了算法套路,还可以顺便去 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 公众号查看,关注后可直接搜索本站内容:

Copyright © labuladong 2020 all right reserved,powered by Gitbook该文件修订时间: 2021-04-19 18:19:20

results matching ""

    No results matching ""