题解 | 判断是不是二叉搜索树

1、解题思路

1. 递归方法（中序遍历验证）： 二叉搜索树的中序遍历结果是一个严格递增的序列。进行中序遍历，记录前一个节点的值，确保当前节点的值大于前一个节点的值。
2. 递归方法（上下界验证）： 每个节点都有一个值的上下界限制。左子树的所有节点值必须小于当前节点值（上界为当前节点值）。右子树的所有节点值必须大于当前节点值（下界为当前节点值）。
3. 迭代方法（中序遍历）： 使用栈模拟中序遍历。检查遍历结果是否严格递增。

2、代码实现

C++（中序遍历递归）

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    bool isValidBST(TreeNode* root) {
        // write code
        if (root == nullptr) {
            return true;
        }

        if (!isValidBST(root->left)) {
            return false;
        }

        if (prev != nullptr && root->val <= prev->val) {
            return false;
        }

        prev = root;

        return isValidBST(root->right);
    }

  private:
    TreeNode* prev = nullptr;
};

C++（上下界递归）

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    bool isValidBST(TreeNode* root) {
        // write code here
        return helper(root, nullptr, nullptr);
    }

    bool helper(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
        if (root == nullptr) {
            return true;
        }

        if ((minNode != nullptr && root->val <= minNode->val) || (maxNode != nullptr &&
                root->val >= maxNode->val)) {
            return false;
        }

        return helper(root->left, minNode, root) && helper(root->right, root, maxNode);
    }
};

C++（中序遍历迭代）

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    bool isValidBST(TreeNode* root) {
        // write code here
        stack<TreeNode*> s;
        TreeNode* prev = nullptr;

        while (root != nullptr || !s.empty()) {
            while (root != nullptr) {
                s.push(root);
                root = root->left;
            }

            root = s.top();
            s.pop();

            if (prev != nullptr && root->val <= prev->val) {
                return false;
            }
            prev = root;

            root = root->right;
        }

        return true;
    }
};

Java（中序遍历递归）

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        // write code here
        if (root == null) return true;

        if (!isValidBST(root.left)) return false;

        if (prev != null && root.val <= prev.val) return false;
        prev = root;

        return isValidBST(root.right);
    }

    TreeNode prev = null;
}

Java（上下界递归）

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        // write code here
        return helper(root, null, null);
    }

    private boolean helper(TreeNode root, TreeNode minNode, TreeNode maxNode) {
        if (root == null) return true;

        if ((minNode != null && root.val <= minNode.val) ||
                (maxNode != null && root.val >= maxNode.val)) {
            return false;
        }

        return helper(root.left, minNode, root) && helper(root.right, root, maxNode);
    }
}

Python（中序遍历递归）

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
class Solution:
    def __init__(self):
        self.prev = None

    def isValidBST(self , root: TreeNode) -> bool:
        # write code here
        if not root:
            return True
        
        if not self.isValidBST(root.left):
            return False
        
        if self.prev is not None and root.val <= self.prev.val:
            return False
        self.prev = root
        
        return self.isValidBST(root.right)

Python（上下界递归）

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
class Solution:
    def isValidBST(self , root: TreeNode) -> bool:
        # write code here
        return self.helper(root, None, None)
    
    def helper(self, root, min_node, max_node):
        if not root:
            return True
        
        if (min_node is not None and root.val <= min_node.val) or \
           (max_node is not None and root.val >= max_node.val):
            return False
        
        return self.helper(root.left, min_node, root) and \
               self.helper(root.right, root, max_node)

3、复杂度分析

• 时间复杂度：O(n)，每个节点被访问一次。
• 空间复杂度：递归方法为 O(h)（树高），迭代方法为 O(n)（栈存储节点）。