No. 98 - Validate Binary Search Tree

---

LeetCode 98 – Validate Binary Search Tree

題目描述

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid 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.

---

首先我們要了解什麼是 binary search tree (BST)。BST 的定義是 tree 中的每一個 node 其左 subtree 的所有 nodes 都要比它小，其右 subtree 的所有 node 都要比它大，同時它的左右 subtree 也要是 BST。

另外，BST 中的 node 不會有一樣的值不然就不滿足前面的定義了。

本題我們會有解釋兩種做法，一種是 recursive 去判別每個 node 是否符合定義，另一種則是利用 BST 的特性以 iterative 作法來解。

解法 1. Iterative Approach

我們其實可以發現一件事，若是把 BST 壓扁變成一條線，它在線上就是從左到右由小到大，如下圖所示:

其中 a-g 就是由小到大的值，這樣才符合 BST 的定義。

所以我們可以使用 inorder traversal 的作法來把 BST 的 node 存成一個 list，在判斷這個 list 是否由小到大便可判斷其是否為 BST。

完整的程式碼如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traversal(TreeNode *node, vector<int> &res) {
      if (!node)
        return;
      // inorder traversal
      traversal(node->left, res);
      res.push_back(node->val);
      traversal(node->right, res);
    }
    bool isValidBST(TreeNode* root) {
      vector<int> sort_list;
      traversal(root, sort_list);
      int i = 0;
      while (i < sort_list.size() - 1) {
        if (sort_list[i] >= sort_list[++i])
          return false;
      }
      return true;
      
    }
};

解法 2. Recursive Approach

我們需要一個 recursive 的函式從 root 開始 recursive 分別往左右 node 去比較其是否符合 BST 的定義，函式內容如下：

bool _isValidBST(TreeNode *node, TreeNode *max_node, TreeNode *min_node) {
      if (!node)
        return true;
      if (max_node && node->val >= max_node->val)
        return false;
      if (min_node && node->val <= min_node->val)
        return false;
      return _isValidBST(node->left, node, min_node) &&
             _isValidBST(node->right, max_node, node);
    }

_isValidBST 函式有三個參數 node, max_node, min_nod。node 是要被檢查是否滿足 BST 定義，而檢查的方法就是跟 max_node 或 min_node 進行比較，max_node, min_node 其實就是當前 node 的上面的 parents，由前面解法 1 有提到，BST 其實就像是一條由小到大的線，所以任意的 node 必定會被夾擠在上面 parents 的中間。

上面程式碼第二行首先確認這個 node 存不存在，如果不存在代表已經走到底了都沒有發現不符合 BST 的情況就回傳 true。

接著 4-7 行就是在檢查這個 node 是否在其 parents 的中間沒有超出範圍。

而這邊的一個重點就是 max_node 跟 min_node 是代表哪一個 parent node，這在第 8 行我們可以看到，下一次呼叫 _isValidBST 其 node 為當前 node 的 left child 或 right child，這邊 left child 跟 right child 都要呼叫一次，但這裡會有兩種情況。

第一種是下一次 recursive 傳入的是 left child，這代表當前 node 必須要是後面 left subtree 的最大值，所以 max_node = node。

第二種是下一次 recursive 傳入的是 right child，這代表當前 node 必須要是後面 right subtree 的最小值，所以 min_node = node。

如此每次 recursive 便能檢查當前 node 是否在規定的範圍內。完整的程式碼如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool _isValidBST(TreeNode *node, TreeNode *max_node, TreeNode *min_node) {
      if (!node)
        return true;
      if (max_node && node->val >= max_node->val)
        return false;
      if (min_node && node->val <= min_node->val)
        return false;
      return _isValidBST(node->left, node, min_node) &&
             _isValidBST(node->right, max_node, node);
    }
    bool isValidBST(TreeNode* root) {
      return _isValidBST(root, nullptr, nullptr);
    }
};

複雜度分析

時間複雜度上，要確認是否為 BST 就必須每個 node 都檢查一遍，所以複雜度都為 \(O(N)\)，但差別在於解法 1 是先把每個 node 都存到 list 在把 list 從頭到尾檢查一遍大小。分的詳細的話，解法 1 是 \(O(2N)\)。

空間複雜度上，解法 1 需要存所有的 nodes 複雜度為 \(O(N)\)，而 recursive 的解法是要存函式的 stack，所以複雜度為 \(O(H)\)，\(H\) 為 tree 高。