iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 17
3
Software Development

從LeetCode學演算法系列 第 17

[Day 17] 從LeetCode學演算法 - 0098. Validate Binary Search Tree (Medium)

目標:
這題主要目的在於介紹二元樹中最常見實用的類別:二元搜尋樹
(Binary Search Tree)

原題:

Question:
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:
    2
   / \
  1   3
Input: [2,1,3]
Output: true
Example 2:
    5
   / \
  1   4
     / \
    3   6
Input: [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.

分析/解題:
題目給定一個二元樹,檢查它是否是二元搜尋樹(Binary Search Tree)。
終於我們來到二元樹的進階版了!
二元搜尋樹如同題目說明,要符合以下三個特性:

  1. 任一個節點的左子樹的所有節點值小於該節點自身的值
  2. 任一個節點的右子樹的所有節點值大於該節點自身的值
  3. 二元搜尋樹的左子樹右子樹也都是二元搜尋樹

直觀來說,當我們從某個節點開始往左邊走的時候,一定要比自己小;
反之往右邊走的時候,要比自己大。也因為這個特性,當這棵樹足夠平衡時
(節點分布的很均勻時),會相當有利於搜尋值,
因為每次都幾乎可以排除掉一半的可能性

以下面的圖來說,我們想要從一個有15個節點的二元搜尋樹找到58這個值,
就要從根節點開始,每次比較大小,若58比較大就往右邊走,
比較小就往左邊走,直到找到剛好的值,或是碰到NIL(沒有別的節點可以搜尋)為止。

可以看到圖中由於深度一樣的關係,不論搜尋什麼值,
我們可以預期最多就只需要4次的比對就可以找出任意一個值是否在這棵樹裡面;
每次刪去一半的可能性,所以如果總節點有N個的話,
搜尋的複雜度最高即為O(logN)

(記得我們提過二元樹不一定非得要全部都有連接節點,
這個結果是建立在這棵二元搜尋樹是**平衡(balanced)**的狀況,
如果這棵樹全部都改成只有左邊的節點的話,結果可是會變成O(N)的!)


(Binary Serach Tree (Balanced, Complete, Perfect))

我們同樣以上面這棵樹為例,
如果我們想知道它從小到大的節點怎麼排序呢?
這裡就需要使用到In-order Traversal了。
In-order的順序為左-中-右,代表每次我們目標要先拿到左邊的值,
接著是中間,最後才是右邊的值;
我們最後希望拿到的是
[18, 20, 22, 33, 36, 37, 38, 43, 52, 54, 58, 61, 63, 66, 68]的話,
我們要先一路走到最左邊的節點,代表左邊沒有更小的值了,
才能將其印出來(18),接著第二小的值則是最左邊節點的父節點(20),
而對33來說,還有20的右節點22比它還要小,
最後以此類推,每次找到下一個最小值。
寫成虛擬碼如下:

inorder(root) {
  if root == NIL return
  inorder(root.left)
  print(root.val)
  inorder(root.right)
}

讀者可以嘗試使用上面的遞迴的方式走過一遍,相信會較為理解這整個流程。
留意上面由於當發現NIL的時候就直接return回到了遞迴的上一層,
所以就會造成類似往上走一層的效果。

回到我們的題目,我們已經知道在In-order的狀況下,
對於二元搜尋樹可以得到一個由小到大的順序

所以只要記住上一個節點,每次去比較上一個節點和現在走到的節點,
當現在的節點跟上一個節點相比較小或相等時,
表示這不是二元搜尋樹(因為越後面的節點必須較大才行);
反之,當每個節點都走完沒有錯誤時,
這時候就可以確認這個二元樹是二元搜尋樹了。

寫成虛擬碼如下:

let last = NIL
isValidBST(root) {
   if root == NIL return true
   if !isValidBST(root.left) return false
   if last != NIL and root.val <= last.val return false
   last = root // 更新上一個節點的位置
   return isValidBST(root.right)
}

Java的寫法部分,我們可以宣告一個class的變數last,
用來存放上一個走到的節點(放在函式內部的話會被洗掉)

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode last;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST(root.left)) return false;
        if (last != null && root.val <= last.val) return false;
        last = root;
        return isValidBST(root.right);
    }
}

Python的部分,請留意到記得在呼叫時使用self的關鍵字,
否則可能會無法在isValidBST中取得last。

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.last = None
    def isValidBST(self, root: TreeNode) -> bool:
        if not root: return True
        if not self.isValidBST(root.left): return False
        if self.last and root.val <= self.last.val: return False
        self.last = root
        return self.isValidBST(root.right)

面試實際可能會遇到的問題:
「時間/空間複雜度?」
(O(N), O(1),因為要走過整個BST,
但除了幾個變數外,不需額外的資料結構)

「可否不用遞迴呢?」
(可以,使用Stack,可以用迴圈讓每次先將root塞入,一路向左邊走將每個左節點放入Stack中,接下來同樣每次取出一個節點,判斷和前一個的大小比較。最後每個左側處理完以後,再將位置移向右節點,迴圈重複即可。)

「可以不用class的變數來解此題嗎?」
(可以,有一種解法是記錄對某個節點的最小值最大值限制,
將遞迴函式增加為傳入root, min, max
並隨著每次看到的節點更新其底下的限制條件,
這樣就不需要按照in-order的方式移動,也不需要class的變數。
Java的解法這邊收錄 ryanswizzle在Leetcode的解法如下。)

public class Solution {
  public boolean isValidBST(TreeNode root) {
      return isValid(root, null, null);
  }

  public boolean isValid(TreeNode root, Integer min, Integer max) {
      if(root == null) return true;
      if(min != null && root.val <= min) return false;
      if(max != null && root.val >= max) return false;
    
      return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
  }
}

從LeetCode學演算法,我們下次見囉,掰~

下篇預告:
0094. Binary Tree Inorder Traversal (Medium)


上一篇
[Day 16] 從LeetCode學演算法 - 0136. Single Number (Easy)
下一篇
[Day 18] 從LeetCode學演算法 - 0094. Binary Tree Inorder Traversal (Medium)
系列文
從LeetCode學演算法30

尚未有邦友留言

立即登入留言