面试金典--4.5

题目描述：实现一个函数，检查一颗二叉树是否为二叉查找树

思路：递归判断当前节点以及其左右子树（这种思路是错误的，因为二叉查找树必须左子树所有节点小于等于当前节点；右子树所有节点大于当前节点；）

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 #include <ostream>
 8 #include <vector>
 9 #include <list>
10 #include <cmath>
11 #include <string>
12 #include <stdexcept>
13 #include <stack>
14 using namespace std;
15 
16 typedef struct treeNode
17 {
18     struct treeNode *left;
19     struct treeNode *right;
20     int val;
21     treeNode(int pval):left(NULL),right(NULL),val(pval)
22     {
23 
24     }
25 }Node;
26 
27 bool fun(Node *root)
28 {
29     if(root == NULL)
30         return true;
31     if(root->left != NULL)
32     {
33         if(root->left->val > root->val)
34             return false;
35     }
36     if(root->right != NULL)
37     {
38         if(root->right->val < root->val)
39             return false;
40     }
41     return fun(root->left)&&fun(root->right);
42 }
43 
44 int main()
45 {
46     Node tmp1(1);
47     Node tmp2(2);
48     Node tmp3(3);
49 
50     Node *root = &tmp1;
51 
52     /*root->left = &tmp2;
53     root->right = &tmp3;
54     cout<<fun(root);*/
55 
56     root->right = &tmp2;
57     root->right->right = &tmp3;
58     cout<<fun(root);
59     return 0;
60 }

（1）我们换个角度思考，可以想到中序遍历的方法，当不存在重复元素的时候，中序遍历有序的话那么就是二叉查找树。缺点是没办法处理重复元素的情况

（2）那么有什么可以处理重复的元素算法呢？答案就是，因为对于当前节点，其左子树的值肯定在[INT_MIN,node->val]之间，而右子树的值肯定在(node->val,INT_MAX]之间。

不满足则返回false

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 #include <ostream>
 8 #include <vector>
 9 #include <list>
10 #include <cmath>
11 #include <string>
12 #include <stdexcept>
13 #include <stack>
14 using namespace std;
15 
16 typedef struct treeNode
17 {
18     struct treeNode *left;
19     struct treeNode *right;
20     int val;
21     treeNode(int pval):left(NULL),right(NULL),val(pval)
22     {
23 
24     }
25 }Node;
26 
27 bool fun(Node *root,int minVal,int maxVal)
28 {
29     if(root == NULL)
30         return true;
31     if(root->val > maxVal || root->val <= minVal)
32         return false;
33     return fun(root->left,minVal,root->val)&&fun(root->right,root->val,maxVal);
34 }
35 
36 int main()
37 {
38     
39     return 0;
40 }