iT邦幫忙

2021 iThome 鐵人賽

DAY 11
0
自我挑戰組

快樂社畜路:畢業後的後端開發求職準備系列 第 11

【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

碎念

我要開始另外一個系列了,
因為誤會結果這個系列沒有團報到QQ
反正本來就是自我挑戰,
應該不會誤人子弟ㄅ。


上一篇
【LeetCode】Binary Tree
下一篇
【LeetCode】Binary Search
系列文
快樂社畜路:畢業後的後端開發求職準備30

尚未有邦友留言

立即登入留言