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

更新 發佈閱讀 3 分鐘
raw-image

題目在這裡: Validate Binary Search Tree

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

題目也給了BST的定義:

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

測試範例

Example 1:

raw-image
Input: root = [2,1,3]
Output: true

Example 2:

raw-image
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拜訪整顆樹,那拜訪的軌跡剛好會從小到大排列。

因此,我們可以先給定一個上、下邊界,分別是(最小正整數最大正整數)來包住整顆樹的合理值的範圍,接著不斷依照當下節點的值動態更新對應的(下區間,上區間),最後遞迴檢查左子樹和右子樹。

raw-image


假如過程中發現有一個節點的值超出合理範圍,就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

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
96會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/09/26
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Thumbnail
2024/09/26
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Thumbnail
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/09
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Thumbnail
2024/09/09
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Thumbnail
看更多
你可能也想看
Thumbnail
在小小的租屋房間裡,透過蝦皮購物平臺採購各種黏土、模型、美甲材料等創作素材,打造專屬黏土小宇宙的療癒過程。文中分享多個蝦皮挖寶地圖,並推薦蝦皮分潤計畫。
Thumbnail
在小小的租屋房間裡,透過蝦皮購物平臺採購各種黏土、模型、美甲材料等創作素材,打造專屬黏土小宇宙的療癒過程。文中分享多個蝦皮挖寶地圖,並推薦蝦皮分潤計畫。
Thumbnail
小蝸和小豬因購物習慣不同常起衝突,直到發現蝦皮分潤計畫,讓小豬的購物愛好產生價值,也讓小蝸開始欣賞另一半的興趣。想增加收入或改善伴侶間的購物觀念差異?讓蝦皮分潤計畫成為你們的神隊友吧!
Thumbnail
小蝸和小豬因購物習慣不同常起衝突,直到發現蝦皮分潤計畫,讓小豬的購物愛好產生價值,也讓小蝸開始欣賞另一半的興趣。想增加收入或改善伴侶間的購物觀念差異?讓蝦皮分潤計畫成為你們的神隊友吧!
Thumbnail
題目給定一個布林代數的二元樹,要求我們計算最後的結果。 葉子節點都是真假值 非葉子節點都是布林運算子
Thumbnail
題目給定一個布林代數的二元樹,要求我們計算最後的結果。 葉子節點都是真假值 非葉子節點都是布林運算子
Thumbnail
這篇文章,會帶著大家複習以前學過的二元搜尋樹(Binary Search Tree)框架, 並且以二分搜尋樹的概念與定義為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 二元搜尋樹(Binary Search Tree)的定義
Thumbnail
這篇文章,會帶著大家複習以前學過的二元搜尋樹(Binary Search Tree)框架, 並且以二分搜尋樹的概念與定義為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 二元搜尋樹(Binary Search Tree)的定義
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們判定這是否為一顆合法的奇偶二元樹? 奇偶二元樹的定義: 從上到下依序是第0層、第一層、...、第n層 偶數層裡面的節點值都必須是奇數,而且由左到右嚴格遞增。 奇數層裡面的節點值都必須是偶數,而且由左到右嚴格遞減。 題目的原文敘述 測試
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們判定這是否為一顆合法的奇偶二元樹? 奇偶二元樹的定義: 從上到下依序是第0層、第一層、...、第n層 偶數層裡面的節點值都必須是奇數,而且由左到右嚴格遞增。 奇數層裡面的節點值都必須是偶數,而且由左到右嚴格遞減。 題目的原文敘述 測試
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們找出這棵二元樹最後一層最左邊的值。 題目的原文敘述 測試範例 Example 1: Input: root = [2,1,3] Output: 1 Example 2: Input: root = [1,2,3,4,null,5,6
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們找出這棵二元樹最後一層最左邊的值。 題目的原文敘述 測試範例 Example 1: Input: root = [2,1,3] Output: 1 Example 2: Input: root = [1,2,3,4,null,5,6
Thumbnail
題目敘述 題目會給我們一棵BST二元搜索樹的根結點root,還有一個指定的目標值key。 要求我們在樹中刪除帶有這個key值的節點,並且返回更新過後二元搜索樹的樹根root。 題目的原文敘述 測試範例 Example 1: Input: root = [5,3,6,2,4,null,
Thumbnail
題目敘述 題目會給我們一棵BST二元搜索樹的根結點root,還有一個指定的目標值key。 要求我們在樹中刪除帶有這個key值的節點,並且返回更新過後二元搜索樹的樹根root。 題目的原文敘述 測試範例 Example 1: Input: root = [5,3,6,2,4,null,
Thumbnail
題目敘述 題目會給我們一棵二元搜索樹的根結點root,還有一個指定的目標值val。 要求我們找出在樹中對應到目標值val的節點,假如找不到,請回傳null( null在Python就是None)。 題目的原文敘述 測試範例 Example 1: Input: root = [4,2,
Thumbnail
題目敘述 題目會給我們一棵二元搜索樹的根結點root,還有一個指定的目標值val。 要求我們找出在樹中對應到目標值val的節點,假如找不到,請回傳null( null在Python就是None)。 題目的原文敘述 測試範例 Example 1: Input: root = [4,2,
Thumbnail
題目敘述 題目會給定一個二元樹的樹根結點Root node,要求我們計算這顆二元樹的最大深度是多少? 二元樹的深度的定義: 從根結點到葉子結點的最大路徑長度。 題目的原文敘述 約束條件 Constraints: The number of nodes in the tree is
Thumbnail
題目敘述 題目會給定一個二元樹的樹根結點Root node,要求我們計算這顆二元樹的最大深度是多少? 二元樹的深度的定義: 從根結點到葉子結點的最大路徑長度。 題目的原文敘述 約束條件 Constraints: The number of nodes in the tree is
Thumbnail
題目敘述 題目會給我們一顆二元樹的根結點,請我們列出每一層最右邊的節點值,以陣列的形式返回答案。 題目的原文敘述 測試範例 Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] 每一層最右邊的節點值分別是1, 3,
Thumbnail
題目敘述 題目會給我們一顆二元樹的根結點,請我們列出每一層最右邊的節點值,以陣列的形式返回答案。 題目的原文敘述 測試範例 Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] 每一層最右邊的節點值分別是1, 3,
Thumbnail
題目敘述 題目會給定我們一顆二元搜索樹BST的根結點, 還有一個指定區間的上邊界R 和 下邊界L。 請問二元搜索樹中,所有落在指定區間內的節點元素值的總和是多少? 題目的原文敘述 測試範例 Example 1: Input: root = [10,5,15,3,7,null,18], l
Thumbnail
題目敘述 題目會給定我們一顆二元搜索樹BST的根結點, 還有一個指定區間的上邊界R 和 下邊界L。 請問二元搜索樹中,所有落在指定區間內的節點元素值的總和是多少? 題目的原文敘述 測試範例 Example 1: Input: root = [10,5,15,3,7,null,18], l
Thumbnail
題目會給定一顆二元樹的根結點,要求我們驗證這一顆樹是否為合法的二元搜索樹, 也就是所謂的Binary search tree, aka BST?
Thumbnail
題目會給定一顆二元樹的根結點,要求我們驗證這一顆樹是否為合法的二元搜索樹, 也就是所謂的Binary search tree, aka BST?
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News