@@ -0,0 +1,1757 @@
+/**%0A *%09Given a binary tree, determine if it is a valid binary search tree (BST).%0A *%0A *%09Assume a BST is defined as follows:%0A *%0A *%09The left subtree of a node contains only nodes with keys less than the node's key.%0A *%09The right subtree of a node contains only nodes with keys greater than the node's key.%0A *%09Both the left and right subtrees must also be binary search trees.%0A *%0A *%09An example:%0A *%0A * %09   %09%091%0A *%09 %09   / %5C%0A *%09%09  2   3%0A *  %09%09 /%0A * %09%09%094%0A * %09%09%09 %5C%0A *  %09 %09  5%0A *%09The above binary tree is serialized as %7B1,2,3,#,#,4,#,#,5%7D.%0A *%0A *%09Author: matao%09%0A *%0A */%09%0A%0Aclass TreeNode %7B%0A%09int val;%0A%09TreeNode left;%0A%09TreeNode right;%0A%09TreeNode(int x) %7B val = x; %7D%0A%7D%0A%0Apublic class ValidateBinarySearchTree %7B%0A%09/**%0A%09 *%09wrong answer%0A%09 *  %E4%BB%85%E4%BB%85%E5%88%A4%E6%96%AD%E4%BA%86%E5%B7%A6%E5%8F%B3%E5%AD%A9%E5%AD%90%E7%BB%93%E7%82%B9%E5%B0%8F%E4%BA%8E%E5%A4%A7%E4%BA%8E%E6%A0%B9%E7%BB%93%E7%82%B9%EF%BC%8C%E5%B9%B6%E6%B2%A1%E6%9C%89%E5%88%A4%E6%96%AD%E5%85%B6%E5%B7%A6%E5%8F%B3%E5%AD%90%E6%A0%91%0A%09 *%0A%09 *%09public boolean isValidBST(TreeNode root) %7B%0A%09 *%09%09if(root == null) %7B%0A%09 *%09%09%09return true;%0A%09 *%09%09%7D%0A%09 *%09%09if(root.left != null && root.left.val %3E= root.val) %7B%0A%09 *%09%09%09return false;%0A%09 *%09%09%7D%0A%09 *%09%09if(root.right != null && root.right.val %3E= root.val) %7B%0A%09 *%09%09%09return false;%0A%09 *%09%09%7D%0A%09 *%09%09return isValidBST(root.left) && isValidBST(root.right);%0A     *%09%7D%0A     */%0A%0A%09// %E5%88%A9%E7%94%A8binary search tree%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%E5%90%8E%E9%80%92%E5%A2%9E%E7%9A%84%E7%89%B9%E6%80%A7%0A%09public static boolean isValidBST1(TreeNode root) %7B%0A%09%09List%3CInteger%3E list = new ArrayList%3CInteger%3E();  %0A%09%09inOrderTraversal(root, list);%0A%09%09for (int i = 1; i %3C list.size(); i++) %7B  %0A            if (list.get(i) %3C= list.get(i - 1)) %7B%0A            %09return false;  %0A            %7D%0A        %7D  %0A        return true; %0A%09%7D%0A%0A%09public static void inOrderTraversal(TreeNode root, List%3CInteger%3E list) %7B  %0A        if (root == null) %7B%0A        %09return;  %0A        %7D%0A        inOrderTraversal(root.left, list);  %0A        list.add(root.val);  %0A        inOrderTraversal(root.right, list);  %0A    %7D  %0A%0A%09public static void main(String%5B%5D args) %7B%0A%09%09%0A%09%7D%0A%7D

add Validate Binary Search Tree solution