# **程式筆記(binary search tree)**
:::info
:information_source: 日期 : 2024/03/12
:::
**:thumbsup:** binary search tree基本
BST基本上都要用 **左小右大** 去想
* 最小共同祖先(Lowest Common Ancestor)
給定兩值p和q，若一個root的數值剛好位於p q兩者之間，或p q剛其一剛好等於root數值，那麼p q的最小共同祖先必為root
同理，若p q皆大於(小於)root，那它們的最小共同祖先必在root.right(root.left)
```python
def LCA(self, node):
if not node:
return None
if node.val < p.val and node.val < q.val:
return self.lowestCommonAncestor(node.right, p, q)
elif node.val > p.val and node.val > q.val:
return self.lowestCommonAncestor(node.left, p, q)
else:
return node
```
**BST從小排到大 = inorder**
* inorder排序法 : 左 > 中 > 右
在BST中相當於由小到大的遍歷(也只有BST有這個特點)
```python
def inorderTraversal(self, node):
if not node:
return
self.inorderTraversal(node.left)
self.inorder.append(node.val)
self.inorderTraversal(node.right)
```
* Minimum Absolute Difference in BST
先用inorder traversal(left, root, right)排出順序，然後永遠用後面的減掉前面的
```python
class Solution:
def __init__(self):
self.inorder = []
self.smallest = float("inf")
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
self.inorderTraversal(root)
得到inorder順序
for i in range(1, len(self.inorder)):
self.smallest = min(self.smallest, self.inorder[i] - self.inorder[i - 1])
return self.smallest
```
* Inorder Successor in BST
在inorder排序下，下一個node就是最微微大於自己的那個點
若往下找最後右邊為null，按照中序規則，要找上一個left
若往下找最後左邊為null，按照中序規則，要找middle
```python
class Solution:
def inorderSuccessor(self, root, p):
# 若p(目標物)比現在的node小 -> 往左找 -> 標記結果
# 若p(目標物)比現在的node大 or 相等 -> 往右找
ans = None
while root:
if p.val < root.val:
ans = root
root = root.left
else:
root = root.right
return ans
```
**:thumbsup:** binary search tree 基本2
遞迴tree時間複雜度為樹高h = log(n)
* Convert Sorted Array to Binary Search Tree
先抓中間值，然後不停對左右兩邊做同樣的事情
```python
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
return self.buildBST(nums)
def buildBST(self, num):
if not num:
return None
mid = len(num) // 2
node = TreeNode(val = num[mid])
node.left = self.buildBST(num[:mid])
node.right = self.buildBST(num[mid + 1:])
return node
```
* Validate BST(左右極限)
以它的相對位置判斷(縱軸去看)，從這個node畫縱軸，它的值會被兩條最靠近的縱軸去控制，可以用dfs去實作，每次更新左右邊界
```python
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
l_b, r_b = float("-inf"), float("inf")
return self.check_boundary(root, l_b, r_b)
def checkBoundary(node, l_b, r_b):
if not node:
return True
if not l_b < node.val < r_b:
return False
return self.checkBoundary(node.left, l_b, node.val) and self.checkBoundary(node.right, node.val, r_b)
```
* Binary Search Tree Iterator
先把BST用list儲存起來，再來用index檢查是否合格
```python
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.inorder = []
self.construct(root)
self.i = 0
def construct(self, node):
if not node:
return
self.construct(node.left)
self.inorder.append(node.val)
self.construct(node.right)
return
def next(self) -> int:
ans = -1
if self.i < len(self.inorder):
ans = self.inorder[self.i]
self.i += 1
return ans
def hasNext(self) -> bool:
if self.i < len(self.inorder):
return True
return False
```
* Search in a Binary Search Tree
經典題，在binary tree找數字
記得在traverse過程中，要return結果，因為是recursive，這樣才能層層把答案回傳到最上面的root。
記得在遍歷function裡，連null都要return跟檢查
```python
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return None
def traverse(node):
if not node:
return None
if node.val > val: # go left
return traverse(node.left)
elif node.val < val: # go right
return traverse(node.right)
else: # find !
return node
res = traverse(root)
return res
```
---
**講解連結**
Provided by.
###### tags: `binary search tree` `note` `code`
Sign in with Wallet
Connect another wallet