Lintcode/src/chapter3_binary_tree_and_divide_and_conquer/ValidateBinarySearchTree.java

fishercoder1534 · fishercoder1534 · commit ce8cc929baf4 · 2016-09-08T22:13:24.000-07:00
diff --git a/Lintcode/src/chapter3_binary_tree_and_divide_and_conquer/ValidateBinarySearchTree.java b/Lintcode/src/chapter3_binary_tree_and_divide_and_conquer/ValidateBinarySearchTree.java
@@ -0,0 +1,35 @@
+package chapter3_binary_tree_and_divide_and_conquer;
+
+import classes.TreeNode;
+
+public class ValidateBinarySearchTree {
+
+
+    /**
+     * @param root: The root of binary tree.
+     * @return: True if the binary tree is BST, or false
+     */
+    public static boolean isValidBST(TreeNode root) {
+        if(root == null) return true;
+        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
+    }
+    
+    static boolean dfs(TreeNode root, long min, long max){
+        if(root == null) return true;
+        if( (long) root.val >= max || (long) root.val <= min) return false;
+        boolean left = dfs(root.left, min, root.val);
+        boolean right = true;
+        if(left) right = dfs(root.right, root.val, max);
+        return left && right;
+    }
+    
+
+    
+    public static void main(String...strings){
+        TreeNode root = new TreeNode(2);
+        root.left = new TreeNode(1);
+        root.right = new TreeNode(2);
+        System.out.println(isValidBST(root));
+    }
+
+}
