【LeetCode】Binary Search Tree

突然发现前面应该要多写一点的＠＠
我本来没打算花那麽多篇幅讲 Leetcode...
铁人赛有几篇写得很好，参考那些够看了，不用点进来这篇。

Binary search tree 是一种特别的 Binary tree，
left subtree < root < right subtree，所以可以快速的查找，最惨要找 O(k) 次，k 是树深。

bst 大概有三种类型的题目：

1. 实作 BST

从已排序的 array 和 linkedlist 建造一棵 bst：
108. Convert Sorted Array to Binary Search Tree
109. Convert Sorted List to Binary Search Tree
在 bst 中搜寻：
700. Search in a Binary Search Tree

2. 考 BST 本身

因为他的特殊性质，反而比一般 binary tree 好做事
例如同样是找 LCA，也就是两个节点最近的共同祖先，

235. Lowest Common Ancestor of a Binary Search Tree
236. Lowest Common Ancestor of a Binary Tree
binary search tree 会简单很多。

另外就是写 bst 题目，upperbound lowerbound 要想清楚，
230. Kth Smallest Element in a BST
938. Range Sum of BST
98. Validate Binary Search Tree

3. 需要利用 BST 解题的题型

题目如果有需要一个个加入节点，然後做 binary search 的需求就会用到。
因为考点不是 bst 本身，
通常可以用 bisect module 而不用自己实作，
可以熟悉一下 bisect 有哪些东西好用。

这类题目就不在这里介绍了，通常难度在 medium 以上，并且会有不同的演算法组成 combo 技，例如最常见跟 prefix sum 一起用。

有关 bst 的题目可以从这里看 Binary Search Tree

碎念

我要开始另外一个系列了，
因为误会结果这个系列没有团报到ＱＱ
反正本来就是自我挑战，
应该不会误人子弟ㄅ。