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

考察的知识点：有效搜索二叉树的判断；

解答方法分析：

1. 首先检查根节点是否为空，如果为空则直接返回true，表示空树是有效的二叉搜索树。
2. 然后判断根节点的左子节点和右子节点是否满足二叉搜索树的定义，即左子节点的值小于等于根节点的值，右子节点的值大于等于根节点的值。如果不满足，说明根节点及其子树不是有效的二叉搜索树，直接返回false。
3. 继续递归地判断左子树和右子树是否是有效的二叉搜索树，如果有任何一颗子树不满足，就返回false。
4. 如果整棵树都满足二叉搜索树的定义，就返回true。

所用编程语言：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) {
        if (root == nullptr)
            return true;

        if (root->left != nullptr && root->left->val >= root->val)
            return false;

        if (root->right != nullptr && root->right->val <= root->val)
            return false;

        if (!isValidBST(root->left) || !isValidBST(root->right))
            return false;

        return true;
    }
};