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.

Example 1:

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

Example 2:

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.

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -231 <= Node.val <= 231 - 1

/**
 * 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* root) {
        return isValid(root, nullptr, nullptr);
    }
    bool isValid(TreeNode* root, TreeNode* left, TreeNode* right) {
        if(!root) return true;

        // 其中一個條件不符合就 return false
        // 如果左邊 node 存在，且大於等於 root 的值
        // 如果右邊 node 存在，且 root 的值大於等於右邊 node 的值
        if((left && left->val >= root->val) || right && root->val >= right->val)
            return false;

        // 走訪左邊的樹，最大值為 root，走訪右邊的樹，最小值為 root
        return isValid(root->left, left, root) && isValid(root->right, root, right);
    }
};

• T: $O(N)$
• S: $O(N)$