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

/**
 * 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==nullptr)
            return true;
        
	  //左右子树不为排序树也直接返回
        bool leftIs=isValidBST(root->left);
        bool rightIs=isValidBST(root->right);
        if(leftIs==false||rightIs==false)
            return false;
	  
	  //判断当前结点是否满足
        else
        {
            TreeNode* btL=root->left;
            TreeNode* btR=root->right;
            while(btL!=nullptr&&btL->right!=nullptr)
            {
                btL=btL->right;
            }
            if(btL!=nullptr&&btL->val>root->val)
                return false;

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

        return true;

    }
};

使用递归的方法解决此问题

1.空树为搜索树

2.如果左右子树不都是搜索树，那么返回false；

否则，判断1.根结点的值是否大于左子树最大值或者左子树为空，2.根结点的值是否小于右子树最小值或者右子树为空

总结：

由于先假定能判断左右子树是否是排序树倒推，这是后序遍历的思想

找排序树最大最小值是容易的