Validate Binary Search Tree

樹的問題用遞迴來解相對上比較直覺，所以先試試遞迴解
拆解到最小單位來找 recursive case: 隨機取樹中一個點，判斷它是否 valid
大部分情況都會有上下限。以左邊的點為例，上限就是父節點的值，下限就是它所在的右子樹的父節點的值，所以這個值必須由上到下一層層傳遞下來。反之，右邊的點的話，就變成上限必須一層層傳遞下來
因為上下限必須用傳遞的，所以寫一個 function node_valid 接受上下限的參數

Python 3 Recursive Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
def isValidBST(self, root: Optional[TreeNode]) -> bool:
    def node_valid(node, floor=float('-inf'), ceiling=float('inf')):
        if not node:
            return True
        v = node.val
        if v <= floor or v >= ceiling:
            return False
        return node_valid(node.left, floor, v) and node_valid(node.right, v, ceiling)
    return node_valid(root)

假設樹有 n 個 node

時間複雜度：O(n)
- 因為每個點都會做一次，而每次的複雜度為 O(1)
- 另一個算法可參考這邊的快速解：
  - node_valid(root) 的遞迴深度為這棵樹的深度，在樹為平衡的情況下，深度為 log2 n，所以複雜度為 O(2^(log2 n)) = O(n)

接下來嘗試用迭代解

可以用跟遞迴類似的思路，只是改成把要處理的 nodes 都放到 stack 裡，然後每次迴圈都從裡面拿一個出來做，一直做到 stack 為空。迴圈裡的內容就是 recursive case
因為 floor 和 ceiling 必須一直傳下去，所以跟 node 一起包成 tuple 放入 stack

Python 3 Iterative Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
def isValidBST(self, root: Optional[TreeNode]) -> bool:
    stack = [(root, float('-inf'), float('inf'))]  # node, floor, ceiling
    while stack:
        node, floor, ceiling = stack.pop()
        if not node:
            continue
        v = node.val
        if v <= floor or v >= ceiling:
            return False
        stack.extend([
            (node.left, floor, v),
            (node.right, v, ceiling)
        ])
    return True

Validate Binary Search Tree

接下來嘗試用迭代解

評論

分類

標籤雲

最新文章

彙整

標籤

最新文章

彙整

標籤

Your browser is out-of-date!