推荐订阅源

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

问题描述：给定一个二叉树，判断它是否是一个合法的二叉查找树。

二叉查找树的定义如上，它的定义本身就是递归的，因此，就可以按照上面的定义来判断。那么，如何来使用开始两条限制条件呢，即关于节点的键的大小次序。

这里采用获取左右子树最小值和最大值的方式，那么可以这样来判断一个二叉树是否是二叉查找树：

（1）左子树的最大值小于当前节点的键值；

（2）右子树的最小值大于当前节点的键值；

（3）左右子树都是二叉查找树。

当然，在判断完了之后，还应该返回本二叉树的最小值和最大值。

代码将情况分成了5中情况：

（1）节点是空节点，只在树本身就是空的情况下；

（2）左右子树都为空，节点是叶子节点，此时它是二叉查找树，并且该树的最小值和最大值都是该节点的值；

（3）左子树为空，右子树不空，此时只要右子树是二叉查找树，并且右子树的最小值大于节点的值，该树即是二叉查找树；

（4）左子树不空，有子树为空，与（3）类似；

（5）左右子树都不空，则只有当左右子树都是二叉查找树，并且左子树的最大值小于该节点的值，右子树的最小值大于节点的值。

class Solution {
public:
    bool isValid(TreeNode *root, int &big, int &small)
    {
        if(root == NULL) {
            return true;
        }
        
        if(root->left == NULL && root->right == NULL) {
            big = root->val;
            small = root->val;
            return true;
        }
        else if(root->left == NULL && root->right) {
            int b = 0, s = 0;
            if(isValid(root->right, b, s) && s > root->val) {
                big = b;
                small = root->val;
                return true;
            }
            else
                return false;
        }
        else if(root->left && root->right == NULL) {
            int b = 0, s = 0;
            if(isValid(root->left, b, s) && b < root->val) {
                big = root->val;
                small = s;
                return true;
            }
            else
                return false;
        }
        
        bool ret = false;
        int b_left = 0, b_right = 0, s_left = 0, s_right = 0;

        if(isValid(root->left, b_left, s_left) && isValid(root->right, b_right, s_right) &&
            b_left < root->val && s_right > root->val)
            ret = true;
            
        big = b_right;
        small = s_left;
        
        return ret;
    }

    bool isValidBST(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int b = 0, s = 0;
        
        return isValid(root, b, s);
    }
};