LeetCode 98. 验证二叉搜索树

98. 验证二叉搜索树

解题思路

1. 前序遍历 → 根节点向下传递范围
2. 中序遍历 → 把二叉搜索树看成一个有序数组

Q: 为什么 Java 等语言要用 long 类型？题目不是只有 int 类型吗？

A: 虽然题目是 int 类型，但开始递归的时候，left 需要比所有节点值都要小，right 需要比所有节点值都要大，如果节点值刚好是 int 的最小值/最大值，就没有这样的 left 和 right 了，所以需要用 long 类型。

参考代码

前序遍历

class Solution {
    public boolean isValidBST(TreeNode root) {
        return solution(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean solution(TreeNode node, long left, long right) {
        if(node == null) {
            return true;
        }
        int val = node.val;
        return left < val &&
            val < right &&
            solution(node.left, left, val) &&
            solution(node.right, val, right);
    }
}

中序遍历

class Solution {
    private long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if(!isValidBST(root.left)) {
            return false;
        }
        if(root.val <= pre) {
            return false;
        }
        pre = root.val;
        return isValidBST(root.right);
    }   
}

后序遍历

class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root)[1] != Long.MAX_VALUE;
    }

    private long[] dfs(TreeNode node) {
        // 空节点哨兵「Long.MIN_VALUE, Long.MAX_VALUE」，不会产生任何约束
        if(node == null) {
            return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};
        }

        long[] left = dfs(node.left);
        long[] right = dfs(node.right);
        long x = node.val;
        if(x <= left[1] || x >= right[0]) {
            return new long[]{Long.MIN_VALUE, Long.MAX_VALUE};
        }
        // return new long[]{Math.max(left[1], x), Math.min(right[0], x)};
        return new long[]{
            Math.min(left[0], Math.min(x, right[0])),
            Math.max(left[1], Math.max(x, right[1]))
        };
    }
}