題目

  • 題目連結
  • 目標函式 : isValidBST(root)
    • Input : root: TreeNode
    • Output : bool

解題概念

  • 題意 : 給定一 Binary Tree 的樹根 root，回傳它是否為一有效的 Binary Search Tree
  • 有效 Binary Search Tree 之定義 :
    • 一 Node 的左子樹只會出現 val $\le$ Node.val 的節點
    • 一 Node 的右子樹只會出現 val $\ge$ Node.val 的節點
    • 左右子樹也必須是 Binary Search Tree

我的寫法

  • 想法 : 判斷是否為 Binary Search Tree，也就是經典的 Inorder Traversal 題型
    • 我這邊使用了 Inorder Traversal 中 Recursion 的版本
    • 只需要判斷 Inorder Traversal 出的結果，是否有依照數字順序 & 是否有重複元素即可
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def isValidBST(self, root):
        
        res = []
        
        # 對 node 進行 Inorder Traversal，並將結果丟入 res 中
        def Inorder(node):
            if not node: return
            Inorder(node.left)
            res.append(node.val)
            Inorder(node.right)

        Inorder(root)

        # 最後判斷 : 
        # 1. res 是否有依照數字升序排列
        # 2. res 是否有重複元素 
        return res == sorted(res) and len(res) == len(set(res))
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 31 ms (faster than 32.38%)
    • Memory Usage: 18.8 MB (more than 6.89%)

解答 or 其他優秀寫法

  • 想法 : 使用了 Inorder Traversal 中 Stack 的寫法
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    def isValidBST(self, root):
        
        if not root: return True

        stack = []
        pre = None

        # 若 Stack 不為空 or root 不為 None
        while len(stack) != 0 or root != None:

            # 先探索到 root 最左下的 Node
            while root != None:
                stack.append(root)
                root = root.left

            # pop 一元素
            root = stack.pop()

            # 與 pre.val 進行比較，若不合理則直接回傳 False
            if pre != None and pre.val >= root.val:
                print("{} >= {}".format(pre.val, root.val))
                return False

            pre = root # pre 取代當前 root
            root = root.right # root 往右下移動
        return True
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 24 ms (faster than 73.56%)
    • Memory Usage: 17.8 MB (more than 49.82%)