經典圖論面試題 Validate Binary Search Tree_Leetcode #98

題目在這裡:

題目會給定一顆二元樹的根結點，要求我們驗證這一顆樹是否為合法的二元搜索樹，也就是所謂的Binary search tree, aka BST?

題目也給了BST的定義:

1. 所有左子樹的節點的值都小於 根節點的值
2. 所有右子樹的節點的值都大於 根節點的值
3. 所有左子樹和右子樹的分支也都遵循相同的規則。

測試範例

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