【leetcode】Validate Binary Search Tree

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.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

思路一：利用递归的思想，任何一个节点必须要在min和max范围内

min和max根据是左子树还是右子树来确定

如果是左子树：

node->left<node

如果是右子树：

node->right>node

递归条件：node->val在min和max范围内，node->left要在min,node->val范围内，node->right要在node->val,max范围内

node->val<max&&node->val>min&&testValid(node->left,node->val,min)&&testValid(node->right,max,node->val);

 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        
14         if(root==NULL)
15         {
16             return true;
17         }
18        
19         if(root->left==NULL&&root->right==NULL)
20         {
21             return true;
22         }
23        
24         //注意如果测试用例含有INT_MAX则，必须采用long long int 才能避免出错
25         return testValid(root,(long long int)INT_MAX+1,(long long int)INT_MIN-1);
26     }
27    
28    
29     bool testValid(TreeNode *node,long long int max, long long int min)
30     {
31         if(node==NULL)
32         {
33             return true;
34         }
35        
36        
37         return node->val<max&&node->val>min&&testValid(node->left,node->val,min)&&testValid(node->right,max,node->val);
38        
39     }
40 };

第二种方法，利用二叉排序树中序遍历结果为递增序列的性质

 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     vector<int> ret_v;
13     bool isValidBST(TreeNode *root) {
14        
15         if(root==NULL)
16         {
17             return true;
18         }
19        
20         ret_v.clear();
21         inOrderTraversal(root);
22        
23         //判断是否递增
24         for(int i=0;i<ret_v.size()-1;i++)
25         {
26             if(ret_v[i]>=ret_v[i+1])
27             {
28                 return false;
29             }
30         }
31         return true;
32     }
33    
34     //中序遍历，记录下数值
35     void inOrderTraversal(TreeNode *root)
36     {
37         if(root==NULL)
38         {
39             return;
40         }
41        
42         inOrderTraversal(root->left);
43         ret_v.push_back(root->val);
44         inOrderTraversal(root->right);
45     }
46 };

第三种：直接在中序遍历中判断：

 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    
13     int ret;
14     bool flag;
15     bool isFirstNode;
16  
17     bool isValidBST(TreeNode *root) {
18        
19         flag=true;
20         //判断是不是第一个被访问的节点
21         isFirstNode=true;
22  
23         inOrderTraversal(root);
24         return flag;
25     }
26    
27     void inOrderTraversal(TreeNode *root)
28     {
29         if(root==NULL)
30         {
31             return;
32         }
33        
34         if(!flag)
35         {
36             return;
37         }
38        
39         inOrderTraversal(root->left);
40        
41         //一旦发现不符合升序，则不是二叉排序树
42         if(!isFirstNode&&ret>=root->val)
43         {
44             flag=false;
45             return;
46         }
47  
48         ret=root->val;
49         isFirstNode=false;
50        
51         inOrderTraversal(root->right);
52     }
53    
54  
55 };