從LeetCode學演算法

0098. Validate Binary Search Tree (Medium)

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

1
2
Input: [2,1,3]
Output: true

Example 2

1
2
3
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)。
終於我們來到二元樹的進階版了！
二元搜尋樹如同題目說明，要符合以下三個特性：

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

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

Binary Serach Tree (Balanced, Complete, Perfect)

以下面的圖來說，我們想要從一個有15個節點的二元搜尋樹找到58這個值，
就要從根節點開始，每次比較大小，若58比較大就往右邊走，比較小就往左邊走，直到找到剛好的值，或是碰到NIL(沒有別的節點可以搜尋)為止 。
可以看到圖中由於深度一樣 的關係，不論搜尋什麼值，我們可以預期最多就只需要4次的比對就可以找出任意一個值是否在這棵樹裡面；每次刪去一半的可能性 ，所以如果總節點有N個的話，搜尋的複雜度最高即為O(logN) 。
(記得我們提過二元樹不一定非得要全部都有連接節點，這個結果是建立在這棵二元搜尋樹是平衡(balanced) 的狀況，如果這棵樹全部都改成只有左邊的節點的話，結果可是會變成O(N)的！)

Binary Search for value 58

我們同樣以上面這棵樹為例，
如果我們想知道它從小到大的節點怎麼排序呢？
這裡就需要使用到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比它還要小，最後以此類推，每次找到下一個最小值。
寫成虛擬碼如下：

1
2
3
4
5
6
inorder(root) {
  if root == NIL return
  inorder(root.left)
  print(root.val)
  inorder(root.right)
}

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

In-order Traversal

回到我們的題目，我們已經知道在In-order的狀況下，對於二元搜尋樹可以得到一個由小到大的順序，所以只要記住上一個節點，每次去比較上一個節點和現在走到的節點，當現在的節點跟上一個節點相比較小或相等時，表示這不是二元搜尋樹(因為越後面的節點必須較大才行)；反之，當每個節點都走完沒有錯誤時，這時候就可以確認這個二元樹是二元搜尋樹了。

寫成虛擬碼如下：

1
2
3
4
5
6
7
8
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

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

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
（O(N), O(1)，因為要走過整個BST，
但除了幾個變數外，不需額外的資料結構）

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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學演算法，我們下次見囉，掰~