|
| 1 | +/* |
| 2 | + Author: King, wangjingui@outlook.com |
| 3 | + Date: Dec 20, 2014 |
| 4 | + Problem: Validate Binary Search Tree |
| 5 | + Difficulty: Medium |
| 6 | + Source: https://oj.leetcode.com/problems/validate-binary-search-tree/ |
| 7 | + Notes: |
| 8 | + Given a binary tree, determine if it is a valid binary search tree (BST). |
| 9 | + Assume a BST is defined as follows: |
| 10 | + The left subtree of a node contains only nodes with keys less than the node's key. |
| 11 | + The right subtree of a node contains only nodes with keys greater than the node's key. |
| 12 | + Both the left and right subtrees must also be binary search trees. |
| 13 | +
|
| 14 | + Solution: Recursion. 1. Add lower & upper bound. O(n) |
| 15 | + 2. Inorder traversal with one additional parameter (value of predecessor). O(n) |
| 16 | + */ |
| 17 | + |
| 18 | +/** |
| 19 | + * Definition for binary tree |
| 20 | + * public class TreeNode { |
| 21 | + * int val; |
| 22 | + * TreeNode left; |
| 23 | + * TreeNode right; |
| 24 | + * TreeNode(int x) { val = x; } |
| 25 | + * } |
| 26 | + */ |
| 27 | +publicclassSolution { |
| 28 | +booleanisValidBSTRe(TreeNoderoot,longleft,longright) |
| 29 | + { |
| 30 | +if(root ==null)returntrue; |
| 31 | +returnleft <root.val &&root.val <right && |
| 32 | +isValidBSTRe(root.left,left,root.val) |
| 33 | + &&isValidBSTRe(root.right,root.val,right); |
| 34 | + } |
| 35 | +publicbooleanisValidBST_1(TreeNoderoot) { |
| 36 | +if (root ==null)returntrue; |
| 37 | +returnisValidBSTRe(root, (long)Integer.MIN_VALUE -1, (long)Integer.MAX_VALUE +1); |
| 38 | + } |
| 39 | +booleanisValidBST(TreeNoderoot) { |
| 40 | +long[]val =newlong[1]; |
| 41 | +val[0] = (long)Integer.MIN_VALUE -1; |
| 42 | +returninorder(root,val); |
| 43 | + } |
| 44 | +booleaninorder(TreeNoderoot,long[]val) { |
| 45 | +if (root ==null)returntrue; |
| 46 | +if (inorder(root.left,val) ==false) |
| 47 | +returnfalse; |
| 48 | +if (root.val <=val[0])returnfalse; |
| 49 | +val[0] =root.val; |
| 50 | +returninorder(root.right,val); |
| 51 | + } |
| 52 | +} |
