2023-09-19|閱讀時間 ‧ 約 25 分鐘

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

raw-image

題目在這裡: Validate Binary Search Tree

題目會給定一顆二元樹的根結點,要求我們驗證這一顆樹是否為合法的二元搜索樹,也就是所謂的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

分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.