二叉树——验证二叉搜索树

题目

算法不是很难，但是这个题有两点我想说。先说第一个，这个题假如不了解二叉搜索树的话，完全按照字面意思去做其实有点绕，不过这个题很重要的一点要理解的是二叉搜索树的中序遍历的是一个有序序列，所以这样做就简化了，下面是我做的方法：

class Solution {
public:
    int lastNum = -2147483648;
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool b1, b2, b3;
        b1 = isValidBST(root->left);
        if (root->val >= lastNum) {
            lastNum = root->val;
            b2 = true;
        }
        else b2 = false;
        b3 = isValidBST(root->right);
        return (b1 && b2) && b3;
    }
};

用lastNum记录遍历得到的前一个数字，然后边遍历边比较就可以。

然后就是第二点，先看官方的最优解：

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

算法思想是一样的，但是比较有意思的是他用到了cpp的函数默认参数的特性。在这里相当于扩展了函数参数，而且还可以赋予初始值，也是一个非常实用的小技巧。