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
| 2 / \ 1 3 Binary tree [2,1,3], return true.
|
Example 2:
1 2 3 4
| 1 / \ 2 3 Binary tree [1,2,3], return false.
|
O(n) time O(1) space recursive solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isValidBST(TreeNode root) { return isValid(root, null, null); } private boolean isValid(TreeNode root, Integer lower, Integer upper) { if (root != null) { return (lower == null || root.val > lower) && (upper == null || root.val < upper) && isValid(root.left, lower, root.val) && isValid(root.right, root.val, upper); } return true; } }
|
Iterative Inorder traversal solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| public boolean isValidBST (TreeNode root){ Stack<TreeNode> stack = new Stack<TreeNode> (); TreeNode cur = root ; TreeNode pre = null ; while (!stack.isEmpty() || cur != null) { if (cur != null) { stack.push(cur); cur = cur.left ; } else { TreeNode p = stack.pop() ; if (pre != null && p.val <= pre.val) { return false ; } pre = p ; cur = p.right ; } } return true ; }
|