98. Validate Binary Search Tree - Medium

前往題目

這題要確認是否是一個Valid的Binary Search Tree，那什麼構成這個樹呢?

思路

1. 任何node的左子樹的node數值都要小於該node
2. 而右子樹的node數值都要大於該node
3. 左右子樹都要是Binary Search Trees

遇到樹，我第一個想法就是recursion，模板大概是:

public void recur(Node node) {
  if (node == null) {
    return;
  }

  left = recur(node.left);
  // 這裡是左跨到右
  right = recur(node.right);
  // 這裡是右邊也走完了，回家
}

而這題我的初始想法是:

• 要檢查數值，還要檢查是否是BST
• 紀錄擁有子樹的node的數值，然後檢查左邊，比較數值，有錯就直接結束；右邊也是一樣
• 檢查是否是BST得用height，左右子樹的高度差不能超過1

但我寫不出來，忘了要怎麼樣才能完美紀錄height，檢查數值我也只寫了一行，完全不確定是否這樣能成功，但我的設想是，left和right後就是到那個擁有left和right的節點。雛形code長這樣，寫到這裡已經20幾分鐘了，直接看答案不浪費時間。

雛形code

class Solution {
    int height = 0;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return false;
        }


        TreeNode left = isValidBST(root.left);
        TreeNode right = isValidBST(root.right);

        // At the node that has left and right subtree
        if (left < root.val && right > root.val) return true;

    }

}

觀看解答後

一如既往地，我先看NeetCode大大的影片 (他的影片永遠都解釋得非常清楚又簡潔，Code也是)

看完後發現我的初始想法有誤，因為我不能只看subtree來比左右大小，這樣有可能造成子樹是ok的，但是子樹的node卻比root還小儘管他是在root的右子樹。所以這裡使用的方法是要檢查與更新範圍，看看node的值是否在這個範圍裡。實際例子參考影片，很清楚。

解法

class Solution {
    public boolean isValidBST(TreeNode root) {
        return valid(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
    }

    public boolean valid(TreeNode node, double leftB, double rightB) {
        // Go back when no more child
        if (node == null) {
            return true;
        }

        // Check each node's children
        // Noted if () without ! is true, doesn't gurantee true
        // so we can only check false condition
        if (!(leftB < node.val && rightB > node.val)) {
            return false;
        }

        // Check left and right nodes if they are in the boundary
        return valid(node.left, leftB, node.val) && valid(node.right, node.val, rightB);
    }

}

1. 使用遞迴，parameters構成一個範圍
2. 檢查node是否null
3. 檢查任一個node的左右child是不是小於或大於自己，不是的話回傳false，因為反之檢查true的情況，那就會出現上述說的左右children可以，但是卻不符合祖父node的狀況，所以這裡只能檢查false的情況。
4. 最後遞迴檢查左子樹以及右子樹，範圍很重要

return valid(node.left, leftB, node.val) && valid(node.right, node.val, rightB);

這裡左子樹的範圍是(左子樹的node，左子樹node的值要大於leftB，但是要小於父節點的值)，右子樹是(右子樹的node，右子樹的node值要大於父節點，並且要小於rightB)

簡單來說其實就是，你要保證左邊比父節點小，右邊比父節點大，而一開始用infinity是因為root有可能是2³¹-1或是-2³¹，所以得有更小的或更大的數來讓他在範圍內。

這樣就定義好範圍了，非常的精妙，到底要怎麼樣才能自己想到這樣的解法呢…連用看的都要花時間理解了。然後這題根本不需要管高度，甚至根本就不用驗證是不是Binary tree，不是很懂，也看不出code裡哪裡可以檢查出是不是Binary tree，這部分依然是未解之謎。