LeetCode: Validate Binary Search Tree

 1 public static boolean isValidBST(TreeNode root) {
 2         ArrayList<Integer> list = new ArrayList<Integer>();
 3         traverse(root, list);
 4         
 5         for (int i=0; i<list.size()-1; i++) {
 6             if (list.get(i) >= list.get(i+1)) {
 7                 return false;
 8             }
 9         }
10         
11         return true;
12     }
13     
14     public static void traverse (TreeNode root, ArrayList<Integer> list) {    
15         if (root != null) {
16             traverse(root.left, list);
17             list.add(root.val);
18             traverse(root.right, list);
19         }
20     }

 1 bool isBSTInOrderHelper(BinaryTree *p, int& prev) {
 2   if (!p) return true;
 3   if (isBSTInOrderHelper(p->left, prev)) {
 4     if (p->data > prev) {
 5       prev = p->data;
 6       return isBSTInOrderHelper(p->right, prev);
 7     } else {
 8       return false;
 9     }
10   }
11   else {
12     return false;
13   }
14 }

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