思路：需要遍歷樹，二叉排序樹的特點是 lchild.key < root.key < rchild.key
那麼我們使用分治思想，先利用上面特點將左右子樹分開，遇到第一個大於root.key的之後(右邊)就是右子樹，那麼當我們在遍歷右子樹的時候如果遇到小於root.key的情況，那麼就是錯誤的序列。
1 #include "stdafx.h"
2 #include<stdio.h>
3
4
5 // BST：Binary Search Tree，二叉搜索樹
6 bool VerifySquenceOfBST(int sequence[], int length)
7 {
8 if(sequence == NULL || length <= 0)
9 return false;
10
11 int root = sequence[length - 1];
12
13 // 在二叉搜索樹中左子樹的結點小於根結點
14 int i = 0;
15 for(; i < length - 1; ++i)
16 {
17 if(sequence[i] > root)
18 break;
19 }
20
21 // 在二叉搜索樹中右子樹的結點大於根結點
22 int j = i ;
23 for(; j < length - 1; ++j)
24 {
25 if(sequence[j] < root)
26 return false;
27 }
28
29 // 判斷左子樹是不是二叉搜索樹
30 bool left = true;
31 if(i > 0)
32 left = VerifySquenceOfBST(sequence, i);
33
34 // 判斷右子樹是不是二叉搜索樹
35 bool right = true;
36 if(i < length - 1)
37 right = VerifySquenceOfBST(sequence + i , length - i - 1) ;
38
39 return (left && right);
40 }
41
42
43 int main()
44 {
45
46 //test1
47 // 10
48 // / \
49 // 6 14
50 // /\ /\
51 // 4 8 12 16
52 int data1[] = {4, 8, 6, 12, 16, 14, 10};
53 int length1 = sizeof(data1) / sizeof(int);
54 printf("test1: ");
55 if(VerifySquenceOfBST(data1, length1))
56 printf("Yes\n");
57 else
58 printf("No\n");
59
60 //test2
61 // 5
62 // /
63 // 4
64 // /
65 // 3
66 // /
67 // 2
68 // /
69 // 1
70
71 int data2[] = {5, 4, 3, 2, 1};
72 int length2 = sizeof(data2)/sizeof(int);
73 printf("test2: ");
74 if(VerifySquenceOfBST(data2, length2))
75 printf("Yes\n");
76 else
77 printf("No\n");
78
79 //test3
80 // 5
81 // / \
82 // 4 7
83 // /
84 // 6
85
86 int data3[] = {4, 6, 7, 5};
87 int length3 = sizeof(data3)/sizeof(int);
88 printf("test3: ");
89 if(VerifySquenceOfBST(data3, length3))
90 printf("Yes\n");
91 else
92 printf("No\n");
93
94 //test4
95 // NULL
96
97 printf("test4: ");
98 if(VerifySquenceOfBST(NULL, 0))
99 printf("Yes\n");
100 else
101 printf("No\n");
102
103 return 0;
104 }
