1 題目描述

2 解法

我的問題是在，我一開始以為，只要把上一個節點，傳下去，跟下一層的節點進行比較就好了。但是我錯了！

我一開始腦子想著

你會發現上圖根本不是正確的二元搜尋樹，因為節點3比root小，不應該出現在右子樹中…所以我就卡住了。

2.2 使用Recursion

其實這題真的目的在於，在左子樹，只要一往右走，就要考慮到根節點的值，不能大於root.val。而在右子樹，只要一往右走，就要考慮到根節點的值，不能小於root.val。我想了好久，都沒想到到底要怎麼樣知道走不同子樹的路線時（在左子樹還是在右子樹），還能知道當前到底走在哪個方向（一往右走，還是一往左走）…直到我試著畫出每個節點的上下限。

你會發現，根本不需要顧慮左還是右子樹，你會發現：

只要是往左走，max一定會更新成parent.val，而min則是繼承自上一層的min。
只要是往右走，min一定會更新成parent.val，而max則是繼承自上一層的max。

然後神奇的事情發生了:

因為在左子樹往右走時，max會一路繼承上一層的max，追溯到源頭就是root! 也就是說，我們在左子樹往右走時，max一定會是root的值。
因為在右子樹往左走時，min會一路繼承上一層的min，追溯到源頭就是root! 也就是說，我們在右子樹往左走時，min一定會是root的值。

寫成python其實就是這樣：


def isValidBST(self, node: Optional[TreeNode], min_val=float('-inf'), max_val=float('inf')) -> bool:
    # 往左走 min繼承上一層的min，max更新成parent.val也就是node
    self.isValidBST(node.left, min_val, node.val)
    # 往右走 max繼承上一層的max，min更新成parent.val也就是node
    self.isValidBST(node.right, node.val, max_val)

那我們接下來考慮一下我們的終止條件：

確保當前節點的值在上下限之間
如果挖到底，就回傳True

def isValidBST(self, node: Optional[TreeNode], min_val=float('-inf'), max_val=float('inf')) -> bool:
    # 如果挖到底，就回傳True
    if not node:
        return True
    # 確保當前節點的值在上下限之間，否則回傳False
    if not (min_val < node.val < max_val):
        return False
    # 如果當前節點的值在上下限之間，就繼續往下挖
    left = self.isValidBST(node.left, min_val, node.val)
    right = self.isValidBST(node.right, node.val, max_val)
    # 確保左右子樹都是合法的二元搜尋樹
    return left and right

2.3 使用Stack

我們也可以考慮使用inorder來解這題，因為inorder是一個遞增的序列，（左 - 中 - 右）我們可以透過 inorder 搭配 stack，把所有節點都走過一遍，並且確保是遞增的序列。每次在pop()出來的時候，我們就可以確保右邊的節點比當前節點大。如果不是就回傳False。

首先，一步步把左邊塞入stack

def isValidBST(self, root: Optional[TreeNode]) -> bool:
    stack = [] 
    pre = None
    while stack: 
        # 一步步把左邊塞入stack
        while root: 
            stack.append(root)
            root = root.left

到最底後，pop()出來，開始確保right比node大

def isValidBST(self, root: Optional[TreeNode]) -> bool:
    stack = [] 
    pre = None
    while stack: 
        while root: 
            stack.append(root)
            root = root.left 
        # 到最底後，pop()出來
        root = stack.pop()
        # 然後跟前一個節點比較，按照inorder，pre < root，如果發生 pre > root 就回傳False
        if pre and pre.val > root.val:
            return False
        # 更新pre
        pre = root
        # 繼續往右走
        root = root.right
    return True