[面试真题] LeetCode：Validate Binary Search Tree

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 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     bool isValidBST(TreeNode *root) {
13         // Start typing your C/C++ solution below
14         // DO NOT write int main() function
15         if(NULL == root){
16             return true;
17         }
18         if(root->left){
19             TreeNode *p = root->left;
20             if(root->val <= p->val){
21                     return false;        
22                 }
23             while(p->right){
24                 if(root->val <= p->right->val){
25                     return false;        
26                 }
27                 p = p->right;
28             }
29         }
30         if(root->right){
31             TreeNode *p = root->right;
32             if(root->val >= p->val){
33                     return false;        
34                 }
35             while(p->left){
36                 if(root->val >= p->left->val){
37                     return false;        
38                 }
39                 p = p->left;
40             }
41         }
42         return isValidBST(root->left) && isValidBST(root->right);
43         
44     }
45 };

Run Status: Accepted!
Program Runtime: 68 milli secs

Progress: 54/54 test cases passed.