LeetCode java_Validate Binary Search Tree[验证二进制搜索树]

　　Validate Binary Search Tree

　　LeetCode原题链接：https://leetcode.com/problems/validate-binary-search-tree/

题目如下图所示：

　　看到题以后，第一个想到的方法就是递归，先check root是否满足BST的条件，然后递归check 左子树和右子树。代码如下：

　　public class Solution {
　　public boolean isValidBST(TreeNode root) {
　　return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
　　}
　　public boolean isValidBSTHelper(TreeNode root, int min, int max){
　　if(root == null){
　　return true;
　　}
　　if(root.val <= min || root.val >= max){
　　return false;
　　}
　　return isValidBSTHelper(root.left, min, root.val) && 
isValidBSTHelper(root.right, root.val, max);
　　}
　　}

　　不过这个方法有一个bug，就是如果节点的value是Integer.MAX_VALUE或者Integer.MIN_VALUE的话，这个代码就错误了。在leetcode某一次升级以后，这个方法也无法accepted了。

　　之后，又想到了一个比较笨的办法，既然是BST，那么它的inorder traversal的结果一定是递增的，只要验证这个条件即可。

　　public class Solution {
　　public boolean isValidBST(TreeNode root) {
　　Stack stack = new Stack();
　　TreeNode cur = root;
　　TreeNode pre = null;
　　while(true) {
　　while(cur != null){
　　stack.push(cur);
　　cur = cur.left;
　　}
　　if(stack.isEmpty()){
　　break;
　　}
　　cur = stack.pop();
　　if(pre!=null && pre.val >= cur.val){
　　return false;
　　}
　　pre = cur;
　　cur = cur.right;
　　}
　　return true;
　　}
　　}

　　话说这个方法确实笨了点，希望以后可以遇到更好的代码。