长大后想做什么？做回小孩！

0%

LeetCode——验证二叉搜索树

发表于 更新于 分类于 Valine：
本文字数： 199

NO.98 验证二叉搜索树 中等

G4KBb8.png

思路一：中序遍历 中序遍历有效的BST可以得到升序序列，如果得到的不是严格升序的序列则BST无效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isValidBST(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    //得到中序遍历序列
    inorderTraversal(root,res);
    //检查序列是否严格升序
    for (int i = 0; i < res.size()-1; i++) {
        if (res.get(i)>=res.get(i+1))return false;
    }
    return true;
}

private void inorderTraversal(TreeNode root, List<Integer> res) {
    if (root==null)return;
    inorderTraversal(root.left,res);
    res.add(root.val);
    inorderTraversal(root.right,res);
}

时间复杂度：O(n) 两次遍历，中序遍历一次，检查序列一次

思路二：中序遍历，一次遍历 其实没必要得到中序序列，在中序遍历的过程中直接进行大小比较即可。

1
2
3
4
5
6
7
8
9
TreeNode next = null;

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

时间复杂度：O(n) 一次遍历

迭代实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isValidBST(TreeNode root) {
    if (root==null)return true;
    Stack<TreeNode> stack=new Stack<>();
    TreeNode next=null;
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root=root.left;
        }
        root=stack.pop();
        if (next!=null&&next.val>=root.val)return false;
        next=root;
        root=root.right;
    }
    return true;
}

就是一道考察中序遍历的题目。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github