98. Validate Binary Search Tree

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:

Input:
    2
   / \
  1   3
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

要驗證BST是否合理可以用inorder traversal去照著順序掃過每個node，同時記錄每個node的前一個node(prev)，這樣在掃描每個node的時候跟前一個node的值比較，如果當前的值沒有大於前一個的值，那就是不合理，直接回傳false。

// Iteration
bool isValidBST(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return true;
    stack<TreeNode*> st;
    TreeNode* prev = nullptr;
    while (root || !st.empty()) {
        while (root) {
            st.push(root);
            root = root->left;
        }
        root = st.top(); st.pop();
        if (prev && root->val <= prev->val) return false;
        prev = root;
        root = root->right;
    }
    return true;
}

// Recursion
bool helper(TreeNode* node, TreeNode*& pre) {
    if (!node) return true;
    if (!helper(node->left, pre)) return false;
    if (pre) {
        if (node->val <= pre->val) return false;
    }
    pre = node;
    return helper(node->right, pre);
}
bool isValidBST(TreeNode* root) { // time: O(n); space: O(n)
    TreeNode *pre = nullptr;
    return helper(root, pre);
}

O(1) space usage的Morris Traversal不能遇到不合理的node就直接返回false，因為這樣中間暫時連接起來的node還沒斷開，必須所有的都掃描一遍然後斷開中間連接的地方，最後才返回true/false。

// Morris Inorder Traversal
bool isValidBST(TreeNode* root) { // time: O(n); space: O(1)
    if (!root) return true;
    TreeNode *cur = root, *pre = nullptr, *parent = nullptr;
    bool res = true;
    while (cur) {
        if (!cur->left) {
            if (parent && parent->val >= cur->val) res = false;
            parent = cur;
            cur = cur->right;
        } else {
            pre = cur->left;
            while (pre->right && pre->right != cur) pre = pre->right;
            if (!pre->right) {
                pre->right = cur;
                cur = cur->left;
            } else {
                pre->right = nullptr;
                if (parent->val >= cur->val) res = false;
                parent = cur;
                cur = cur->right;
            }
        }
    }
    return res;
}

94. Binary Tree Inorder Traversal