【直观算法】二叉搜索树算法总结 | Go Further | Stay Hungry, Stay Foolish

【直观算法】二叉搜索树算法总结 | Go Further | Stay Hungry, Stay Foolish

【阅读内容】结合Leetcode相关算法题总结二叉搜索树的相关算法，包括基本的二叉搜索构建和应用，附带一些关于AVL树，红黑树的基本概念梳理

是什么

二叉搜索树（Binary Search Tree）BST是大名鼎鼎的搜索算法。在算法界，$O(n)$ 到 $O(\log_2 n)$ 的效率优化大多和BST有关

用白话文来说，二叉搜索树是一颗对于所有节点左孩子 ＜ 根，右子树 ＞ 根的二叉树

基本操作

构建

相关例题：108. Convert Sorted Array to Binary Search Tree

已经给出了定义，Leetcode中有一道将升序数组转换成平衡二叉搜索树的题目。根据二叉树遍历一节的内容，中序遍历的顺序是左 ➜ 根 ➜ 右，再结合二叉搜索树的定义。观察知，二叉搜索树的中序遍历就是一个升序数组。那么问题就转换成了，哪颗平衡二叉树的中序遍历是这个升序数组

因为题目要求平衡二叉树，保证所有子树的高度一样，必须二分输入序列

假设输入序列为[-10,-3,0,5,9]，根节点一定在mid = (start + end) // 2 位置，由递归思维：假设再次调用的函数的返回值是已经完成的子树，也就是说只需把[0, mid-1]代表的树作为左子树，和[mid+1, end]代表的树作为右子树即可

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution: def sortedArrayToBST(self, nums): """ :type nums: List[int] :rtype: TreeNode """ if not nums: return None mid = len(nums) // 2 root = TreeNode(nums[mid]) root.left = self.sortedArrayToBST(nums[ : mid]) root.right = self.sortedArrayToBST(nums[mid+1 : ]) return root

Read full article from 【直观算法】二叉搜索树算法总结 | Go Further | Stay Hungry, Stay Foolish