題目在這裡: Validate Binary Search Tree
題目會給定一顆二元樹的根結點，要求我們驗證這一顆樹是否為合法的二元搜索樹，也就是所謂的Binary search tree, aka BST?題目也給了BST的定義:
- 所有左子樹的節點的值都小於 根節點的值
- 所有右子樹的節點的值都大於 根節點的值
- 所有左子樹和右子樹的分支也都遵循相同的規則。
測試範例
Example 1:
Input: root = [2,1,3]
Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
演算法
其實這題有很多種解法，但是剛好二元搜索樹有一個單調遞增的性質。
也就是說，如果使用前面提過的inorder traversal拜訪整顆樹，那拜訪的軌跡剛好會從小到大排列。
因此，我們可以先給定一個上、下邊界，分別是(最小正整數, 最大正整數)來包住整顆樹的合理值的範圍，接著不斷依照當下節點的值，動態更新對應的(下區間，上區間)，最後遞迴檢查左子樹和右子樹。
假如過程中發現有一個節點的值超出合理範圍，就return False，代表這顆樹
不是合法的BST。
假如全部檢查完，所有節點都或在合理範圍，就return True，代表這顆樹是合法的BST。
程式碼
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
# Use maximal system integer to represent infinity
INF = sys.maxsize
def helper(node, lower, upper):
if not node:
# empty node or empty tree
return True
if lower < node.val < upper:
# check if all tree nodes follow BST rule
return helper(node.left, lower, node.val) and helper(node.right, node.val, upper)
else:
# early reject when we find violation
return False
# ----------------------------------
return helper( node=root, lower=-INF, upper=INF )
複雜度分析
時間複雜度:
O( n ) 從根節點，依循DFS框架，拜訪整顆樹，每個節點最多拜訪一次。
空間複雜度:
O(n) 成本耗費在遞迴呼叫時建立的call stack，最深的深度至多可為O(n)，當整顆樹向左歪斜，或者向右歪斜時。
Reference:
[1] Python/JS/Java/Go/C++ O(n) by DFS and rule [w/ Hint] — Validate Binary Search Tree — LeetCode
