leetcode / 算法
  3 minutes read (About 410 words) 0 visits

problem

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

1
2
3
4
5
6
    2
   / \
  1   3

Input: [2,1,3]
Output: true

Example 2:

1
2
3
4
5
6
7
8
    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false

Explanation: The root node’s value is 5 but its right child’s value is 4.

approach 1:中序遍历

遍历后存到array,判断array是否为升序

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {

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

        }
        return true;
    }

    private List<TreeNode> inorder(TreeNode root, ArrayList<TreeNode> list) {
        if (root == null) {
            return list;
        }
        inorder(root.left, list);
        list.add(root);
        return inorder(root.right, list);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 中序遍历,在比较中返回 */
class Solution {
    TreeNode pre;

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

复杂度

  • time:O(n)
  • space:O(n)

approach 2:递归

根据定义,对于左边的右边节点,他的下界是根节点,上界是父节点;右边的左边节点的下界是父节点,上界是父节点

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {

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

    }

    private boolean helper(TreeNode root, long min, long max) {
        if (root == null) {
            return true;
        }

        if (!helper(root.left, min, root.val)) {
            return false;
        }
        if (root.val <= min || root.val >= max) {
            return false;
        }
        if (!helper(root.right, root.val, max)) {
            return false;
        }
        return true;

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {

    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }

    private boolean helper(TreeNode root, Integer min, Integer max) {
        if (root == null) {
            return true;
        }
        if ((min != null && root.val <= min)) {
            return false;
        }

        if (max != null && root.val >= max) {
            return false;
        }

        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }

}

复杂度

  • time:O(n)
  • space:O(n)
  BST, tree
19.二叉树_最近公共祖先:leetcode236
数据库

Comments

  Follow
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×