Given a binary tree, determine if it is a valid binary search tree (BST).

我想到了用中序遍历，保存到一个数组中，再检查数组是否是有序的。但是我需要O(n)的额外空间保存这个数组。

网上看到一种和这个一样的方法，但是不需要额外空间，但是没太看懂。

1 public static boolean isValidBST(TreeNode root) { 2         ArrayList
     
       list = new ArrayList
      
       (); 3         traverse(root, list); 4          5         for (int i=0; i
       
        = list.get(i+1)) { 7                 return false; 8             } 9         }10         11         return true;12     }13     14     public static void traverse (TreeNode root, ArrayList
        
          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 };