重启DAY8 验证二叉搜索树

跟着灵茶山艾府大佬学习算法思路的day8，目标是在一个月内掌握hot100

b站链接如下：

验证二叉搜索树【基础算法精讲 11】

验证二叉搜索树 题目描述：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 严格小于 当前节点的数。
• 节点的右子树只包含 严格大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

思路：

主要有三种做法，分别是前序、中序和后续遍历。

前序遍历的方法是先访问节点值，再递归左右子树，可以发现每个节点的节点之值一定是大于自己的左侧节点，小于自己的右侧节点的，所以可以通过每个节点的值所在的区间情况，来判断这个节点符不符合二叉搜索树的定义。

中序的方法需要记录下来当前节点的值，然后让下一个节点值和它比较大小。

后序遍历是将节点值的范围往下传，不断细分；后序遍历可以将节点值的范围往上传，而且要注意，对于左子树，只返回一个最大值，右子树只返回一个最小值，是不能组成合理的范围的。比如把节点4换成节点6，如果只传入左边最大值，右边最小值，左边4（6）节点往上传的区间是【3,6】，但是节点2往上传的区间就变成了【1,3】，这是错误的。

因为检查当前节点时确实只需要 lMax和 rMin，但向上级父节点返回时还需要这个节点整个子树的范围信息（包含了左子树和右子树）。比如我们只返回当前节点左子树的最大值，那以这个节点构成的树也许是他父节点的右子树，这样父节点就相当于丢失了右子树的最小值，就可能不满足二叉搜索树了。第二个点是为什么改成区间就可以了，因为改成区间的话，这样整颗树的最小值最大值的信息涵盖了，不存在丢失的问题。

实际上，如果一棵树是二叉搜索树，只返回左子树最大值和右子树最小值也是可以的，会符合条件，因为这就是二叉搜索树的定义。但如果一棵树不是二叉搜索树，采用这种方式就会丢失一些不符合定义的节点（例如将4改为6）。

代码：

前序遍历解法：

var isValidBST = function(root, left=-Infinity, right=Infinity) {
    if (root == null) {
        return true;
    }
    const x = root.val;
    return left < x && x < right &&
           isValidBST(root.left, left, x) &&
           isValidBST(root.right, x, right);
};

中序遍历解法：

var isValidBST = function(root) {
    let prev = null;  // 记录前一个节点的值，此处节点也可以定义为负无穷，那么下面检查节点的循环就无需检测是否为null
    
    function inorder(node) {
        if (!node) return true;
        
        // 遍历左子树
        if (!inorder(node.left)) return false;
        
        // 检查当前节点：中序遍历应该严格递增
        if (prev !== null && node.val <= prev) {
            return false;
        }
        prev = node.val;
        
        // 遍历右子树
        return inorder(node.right);
    }
    
    return inorder(root);
};

后序遍历解法：

var isValidBST = function(root) {
    function dfs(node) {
        if (node == null) {
            return [Infinity, -Infinity];  // 空节点处理
        }
        
        const [lMin, lMax] = dfs(node.left);    // 左子树
        const [rMin, rMax] = dfs(node.right);   // 右子树
        
        const x = node.val;  // 当前节点值
        
        // 检查当前节点是否违反BST规则
        if (x <= lMax || x >= rMin) {
            return [-Infinity, Infinity];  // 返回特殊值表示无效
        }
        
        // 返回当前子树的最小值和最大值
        return [Math.min(lMin, x), Math.max(rMax, x)];
    }
    
    return dfs(root)[1] !== Infinity;  // 检查根节点返回
};

总结：

借用一下灵神的点评：

这个后序还挺不好理解的，后面继续做做相关的。