LeetCode 98. 验证二叉搜索树

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

示例1:

输入:
    2
   / \
  1   3
输出: true

示例2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 1. 递归法

思路：

1. 递归终止条件为当前节点为空
2. 判断当前节点是否满足二叉树性质（左子树都小于根节点 & 右子树都大于根节点）
3. 递归判断左右子树是否满足条件

• 注意：要判断右子树中所有节点都要大于根节点才可以

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

    private boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }

复杂度分析：

• 时间复杂度：O(n), 需要遍历所有节点进行判断

• 空间复杂度：O(n), 递归深度可能达到n层

• 2. 迭代法

需要使用（中序遍历）LeetCode 94. 二叉树的中序遍历 - 简书

思路： 二叉搜索树中序遍历后的结果一定是从小到达排列的

public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        long res = Long.MIN_VALUE;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (cur.val < res) return false;
            else res = cur.val;
            cur = cur.right;
        }
        return true;
    }

复杂度分析：

• 时间复杂度：O(n), 最坏情况下我们需要遍历每个元素添加到stack中

• 空间复杂度：O(n), 栈中需要存储 n 个元素

• 3. 中序遍历

思路：

1. 创建 list，递归进行中序遍历，将每个节点的值添加到 list中
2. 遍历 list， 判断是否是从小到大进行排序的，如果是则一定是二叉搜索树，否则一定不是

public boolean isValidBST(TreeNode root) {
        List<Long> list = new ArrayList<>();
        helper(root, list);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) - list.get(i - 1) <= 0) return false;
        }
        return true;
    }

    private void helper(TreeNode root, List<Long> list) {
        if (root == null) return;
        helper(root.left, list);
        list.add((long) root.val);
        helper(root.right, list);
    }

复杂度分析：

• 时间复杂度：O(n + n), 需要遍历每个节点进行递归比较，最后还需要遍历 list 查看顺序
• 空间复杂度：O(n + n), 中序遍历过程中使用了递归，并且还需要创建大小为 n 的 list

---

• 源码

• 我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正

• Github