---
# System prepended metadata

title: '**程式筆記(binary search tree)**'
tags: [code, note, binary search tree]

---

# **程式筆記(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去實作，每次更新左右邊界
![](https://i.imgur.com/suB1Trw.png =70%x)
```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`