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

考察知识点： 深度优先搜索、递归

题目分析：

 只要该树中的每一个子树（包含本身）都是二叉搜索树，那么原来的树就是一棵二叉搜索树。该题可以使用递归来解。

 使用递归解题时，可以先考虑特殊情况。当root是空树时，满足二叉搜索树的条件。当root有左孩子并且左孩子的值不小于root的值，那么就不满足二叉搜索树的条件。同理，若root有右孩子并且右孩子的值不大于root的值，那么也不满足二叉搜索树的条件。

 而在一般情况下，root的左右孩子结点满足二叉搜索树的情况，下一步就是要确定左右子树是否是二叉搜索树。由于函数isValidBST返回的是一棵树是否是二叉搜索树，可以将左右子树作为根节点进行递归即可解决问题。

所用编程语言： 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
        if (!root) return true;
        if (root->left && root->left->val >= root->val) return false;
        if (root->right && root->right->val <= root->val) return false;
        return isValidBST(root->left) && isValidBST(root->right);
    }
};