给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

Solution

• 递归法
• BST 的每个节点都要大于左子树的节点并且小于右子树的节点
• 以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r) 的范围内

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        lower = float('-inf')
        upper = float('inf')
        def isBST(root, lower, upper):
            if not root:
                return True
            if (root.val <= lower) or (root.val >= upper):
                return False
            return isBST(root.left, lower, root.val) and \
                    isBST(root.right, root.val, upper)
        return isBST(root, lower, upper)
# @lc code=end

cpp

// @lc code=start
/**
 * 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) {
        long long lower = LONG_MIN;
        long long upper = LONG_MAX;
        return isValid(root, lower, upper);
    }

    bool isValid(TreeNode* root, long long lower, long long upper){
        if(root==nullptr)
            return true;
        if(root->val >= upper || root->val <= lower)
            return false;
        return isValid(root->left, lower, root->val) && 
                isValid(root->right, root->val, upper);
    }
};
// @lc code=end

• 利用 BST 中序有序的性质，设置 pre 值 或 pre 节点。

class Solution {
public:
    long long pre = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(root==nullptr) return true;

        bool left = isValidBST(root->left);
        if(pre < root->val)
            pre = root->val;
        else 
            return false;
        
        bool right = isValidBST(root->right);
        
        return left && right;
    }
};

• 迭代法，中序遍历

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        stack<TreeNode *> stack;

        while (cur != nullptr || !stack.empty()) {
            while (cur != nullptr) {
                stack.push(cur);
                cur = cur->left;
            }
            cur = stack.top();
            stack.pop();
            if (pre != nullptr && cur->val <= pre->val){
                return false;
            }
            pre = cur;
            cur = cur->right;
        }
        return true;
    }
};