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

2021年11月24日 阅读数:0
这篇文章主要向大家介绍手把手带你刷二叉搜索树(第一期),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

 

https://labuladong.gitee.io/algo/2/18/24/java

 

读完本文,你不只学会了算法套路,还能够顺便去 LeetCode 上拿下以下题目:node

230.BST第K小的元素(中等)git

538.二叉搜索树转化累加树(中等)算法

1038.BST转累加树(中等)数据结构

———–oop

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

首先,BST 的特性你们应该都很熟悉了:设计

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

二、对于 BST 的每个节点 node,它的左侧子树和右侧子树都是 BST。element

二叉搜索树并不算复杂,但我以为它能够算是数据结构领域的半壁江山,直接基于 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); } 

那么根据这个性质,咱们来作两道算法题。

_____________