题目描述

98. 验证二叉搜索树

思路

这个题思路我想的是错的，对二叉树的定义有所误解。正确的理解是，根节点大于左子树『所有』节点，并且小于右子树『所有』节点。而我的理解是，根节点大于左孩子，并且小于右孩子。我的理解还不到位。这个case过不了。

image.png

有了正确的理解后，代码不会写，怎样描述 root大于左子树『所有』节点这个概念？
看了答案人家都用的上下限，不懂是在干嘛。
呢呢告诉我，描述 root大于左子树『所有』节点 => root大于左子树所有节点最大值，
描述root小于右子树『所有』节点 => root小于右子树所有节点最小值。
很有道理，但是感觉实现起来，也是不够直接，有重复计算。

后来仔细想了下上下限，突然明白了。
如果是二叉搜索树，中序遍历结果是有序的呀，那么每个节点都有左右邻居吧，左右邻居就是他的上下限。
回到上面那个图，为啥这个case不能过，因为6不满足上下限（10，15）这个条件。
用上下限来描述，就很直接，好实现。注意一点，有个case是INT最大值，因此上下限要用long long。

代码

错误的：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        bool left = true;
        bool right = true;
        if (root->left) {
            left = root->left->val < root->val;
        }
        if (root->right) {
            right = root->right->val > root->val;
        }
        return left && right && isValidBST(root->left) && isValidBST(root->right);    
    }
};

正确的

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return within(root, LONG_MIN, LONG_MAX);
    }
    bool within(TreeNode* root, long long min, long long max) {
        if (!root) return true;
        if (root->val <= min || root->val >= max) return false;
        return within(root->left, min, root->val) && within(root->right, root->val, max);
    }
};

总结

思路：引入上下边界（这个思路我觉得挺难想到，我刚看答案一下子还不能理解，上下边界是什么玩意。可能是我思路不开阔，脑子慢半拍）

对于树的每个节点 val ，设其上下边界 low , high。(用 long 防止 INT_MAX 溢出 )
判断根结点时，须满足 low < val < high ，否则返回 false
判断左节点时，仅上界变化 ( 新上界为 high 与 val 较小值。又因 val 必小于 high，故新上界为 val )
判断右节点时，仅下界变化 ( 同理，新下界为 val )