Ming
0%

LeetCode-98

Posted on Edited on In

题目

结果

中序遍历

递归

Snipaste_2020-12-12_10-45-44.png

代码

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    private final List<Integer> list = new LinkedList<>();

    public boolean isValidBST(TreeNode root) {
        dfs(root);
        long pre = Long.MIN_VALUE;
        for (int num : list) {
            if (pre >= num) {
                return false;
            }
            pre = num;
        }
        return true;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

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

复杂度

时间复杂度：O（n）

空间复杂度：O（n）