面试题24：二叉搜索树后序遍历

判断左子树小于根节点，右子树大于根节点，然后递归

 1 bool VerifySquenceOfBST(int sequence[], int length)
 2 {
 3     if(sequence == NULL || length <= 0)
 4         return false;
 5 
 6     int root = sequence[length - 1];
 7 
 8     // 在二叉搜索树中左子树的结点小于根结点
 9     int i = 0;
10     for(; i < length - 1; ++ i)
11     {
12         if(sequence[i] > root)
13             break;
14     }
15 
16     // 在二叉搜索树中右子树的结点大于根结点
17     int j = i;
18     for(; j < length - 1; ++ j)
19     {
20         if(sequence[j] < root)
21             return false;
22     }
23 
24     // 判断左子树是不是二叉搜索树
25     bool left = true;
26     if(i > 0)
27         left = VerifySquenceOfBST(sequence, i);
28 
29     // 判断右子树是不是二叉搜索树
30     bool right = true;
31     if(i < length - 1)
32         right = VerifySquenceOfBST(sequence + i, length - i - 1);
33 
34     return (left && right);
35 }

用容器

 1 bool VerifySquenceOfBST(vector<int> sequence) {
 2     int len = sequence.size();
 3     if (len <= 0)
 4         return false;
 5     if (len <= 2)
 6         return true;
 7     int root = sequence[len - 1];
 8     int i = 0;
 9     for (; i < len - 1; i++)
10     {
11         if (sequence[i] > root)
12             break;
13     }
14     int j = i;    //分割
15     for (; j < len - 1; j++)
16     {
17         if (sequence[j] < root)
18             return false;
19     }
20     bool left = true;
21     if (i > 0)
22     {
23         vector<int> sequence_left(sequence.begin(), sequence.begin() + i);
24         left = VerifySquenceOfBST(sequence_left);
25     }
26 
27     bool right = true;
28     if (i < len - 1)
29     {
30         vector<int> sequence_right(sequence.begin() + i, sequence.end() - 1);
31         right = VerifySquenceOfBST(sequence_right);
32     }
33     return left && right;
34 }