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.

一开始是这样做的：

1 class Solution { 2 public: 3     bool isValidBST(TreeNode* root) { 4        return checkValid(root, INT_MIN, INT_MAX); 5     } 6  7     bool checkValid(TreeNode * root, int left, int right) 8     { 9         if(root == NULL)10             return true;11         return(root->val > left && root->val < right && checkValid(root->left, left, root->val) ]12             && checkValid(root->right, root->val, right));13     }14 };

然而并不能通过，因为leetCode增加了两个新的测试用例，把INT_MAX以及INT_MIN也囊括进去了。

那么就只好用中序遍历的方法来了(一开始想的是先中序遍历一遍，然后根据遍历的到的值是不是升序排列的来判断这个二叉树是不是BST，但是后来发现传入一个引用的参数可以实现一边递归一边比较)，代码如下：

1 class Solution{ 2 public: 3     bool isValidBST(TreeNode* root) { 4         TreeNode * helper = NULL; 5         return inOrder(root, helper); 6     } 7  8     bool inOrder(TreeNode * root, TreeNode * & prev){//注意这里的是引用 9         if(root == NULL)10             return true;11         bool left = inOrder(root->left, prev);12         if(prev != NULL && prev->val >= root->val)13             return false;14         prev = root;15         bool right = inOrder(root->right, prev);16         return left && right;17     }18 };

 

当然上面的也可以采用迭代的方式来做:

1 class Solution { 2 public: 3     bool isValidBST(TreeNode* root) { 4         stack
     
       s; 5         TreeNode * pre = NULL; 6         if(root == NULL) 7             return true; 8         while(root || !s.empty()){ 9             while(root != NULL){10                 s.push(root);11                 root = root->left;12             }13             14             root = s.top();15             s.pop();16             if(pre != NULL && root->val <= pre->val) return false;17 18             pre = root;19             root = root->right;20         }21         return true;22     }23 };
     

 

 

 

下面是java版本的代码，首先还是不可行的Integer.MAX_VALUE方法，但是还是贴下吧：

1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public boolean isValidBST(TreeNode root) {12         return checkValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);13     }14     15     boolean checkValid(TreeNode root, int left, int right){16         if(root == null)17             return true;18         if(root.val <= left || root.val >= right){19             return false;20         }21         return checkValid(root.left, left, root.val) 22             && checkValid(root.right, root.val, right);23     }24 }

那么只有遍历树了，然后来判断, 这里使用非递归的方法来写:

1 public class Solution { 2     public boolean isValidBST(TreeNode root) { 3         Stack
     
       stack = new Stack
      
       (); 4         HashMap
       
         map = new HashMap
        
         (); 5         List
         
           list = new ArrayList
          
           (); 6 if(root == null) 7 return true; 8 stack.push(root); 9 while(!stack.isEmpty()){10 TreeNode node = stack.peek();11 while(node.left != null && !map.containsKey(node.left)){12 stack.push(node.left);13 map.put(node.left, 1);14 node = node.left;15 }16 stack.pop();17 list.add(node.val);18 if(node.right != null && !map.containsKey(node.right)){19 stack.push(node.right);20 map.put(node.right, 1);21 }22 }23 for(int i = 0; i < list.size() - 1; ++i){24 if(list.get(i) >= list.get(i+1))25 return false;26 }27 return true;28 }29 }