題目

LeetCode - 98. Validate Binary Search Tree

解題思路

題目給一顆Binary Search Tree簡稱BST，我們要判斷他是否為Validate!

  • BST定義:
    • 以左邊節點 ( left node ) 作為根的子樹 ( sub-tree ) 的所有值都小於根節點 ( root )
    • 以右邊節點 ( right node ) 作為根的子樹 ( sub-tree ) 的所有值都大於根節點 ( root )
    • 任意節點 ( node ) 的左、右子樹也分別符合 BST 的定義
    • 不存在任何鍵值 ( key/value ) 相等的節點。

這一題可以先用InOrder的方式來Trace這棵樹，對 BST 做 inorder traversal 就是由小到大依序遍歷。將Trace的順序存進一個list，若是符合BST則list裡的數字會由小到大排列，所以只要不符合由小到大排列，就可以確定他是InValidate的BST

  • 前序 (preorder), 中序 (inorder) 和後序 (postorder) 是指遍歷二元樹 (binary tree) 時，父節點相對於左右節點的順序。假設二元樹如下：

    4
    2 6
    1 3 5 7

    則三種遍歷的順序依序為：
  • 前序 (preorder): 中 -> 左 -> 右，4213657
  • 中序 (inorder): 左 -> 中 -> 右，1234567
  • 後序 (postorder): 左 -> 右 -> 中，1325764

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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
class Solution:
    def isValidBST(self, root:Optional[TreeNode]) -> bool:
        output = []
        self.inOrder(root,output)
        for i in range(1,len(output)):
            if output[i-1] >= output[i]:
                return False
        return True
    
    def inOrder(self,root,output):
        if root is None:
            return
        
        self.inOrder(root.left,output)
        output.append(root.val)
        self.inOrder(root.right,output)

Reference