题解 | #牛群中的编号是否有效#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

二叉搜索树，递归

题目解答方法的文字分析

对于一个有效的二叉搜索树，我们需要满足以下条件：

1. 当前节点的值大于其左子树中的所有节点值；
2. 当前节点的值小于其右子树中的所有节点值；
3. 左子树和右子树都必须是有效的二叉搜索树。

基于这些条件，我们可以使用递归的方式来判断二叉树是否是有效的二叉搜索树。对于每个节点，我们需要判断其值是否满足上述两个条件，然后递归地判断其左子树和右子树是否都是有效的二叉搜索树。在递归过程中，我们还需要传递一个范围，确保左子树的节点值小于当前节点值，右子树的节点值大于当前节点值。

例如，对于二叉树 {2, 1, 3}，根节点为 2，它的左子树节点值 1 小于 2，右子树节点值 3 大于 2，同时递归地判断左子树 {1} 和右子树 {3} 也满足二叉搜索树的条件。

本题解析所用的编程语言

C++

完整且正确的编程代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBSTHelper(root, nullptr, nullptr);
    }
    
    bool isValidBSTHelper(TreeNode* node, TreeNode* minNode, TreeNode* maxNode) {
        if (!node) {
            return true;  // 空节点是有效的二叉搜索树
        }
        
        if ((minNode && node->val <= minNode->val) || (maxNode && node->val >= maxNode->val)) {
            return false;  // 节点值超出范围，不是有效的二叉搜索树
        }
        
        // 递归判断左子树和右子树
        return isValidBSTHelper(node->left, minNode, node) && isValidBSTHelper(node->right, node, maxNode);
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！