面试题24:二叉搜索时的后序遍历序列

题目:输入一个整数数组,判断该数组是不是某二叉搜索时的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任一两个数字都不相同。


分析

我们先假设该数组是某颗二叉搜索树的后序遍历序列,则它有如下性质:

  • 数组最后一个元素是该二叉树的根节点;
  • 若数组为arr,长度为n,则arr[0..k-1]<arr[n-1],arr[k..n-2]>arr[n-1],(0<=k<=n-1);
  • 对arr[0..k-1]和arr[k..n-2]同样适用于这些规律; 不难看出,这是一个递归的思想。数组中前面一部分数字会小于最后一个数字(对应于根节点的左子树),后面一部分数字会大于最后一个数字(对应于根节点的右子树),因此可以递归地对他们进行判断。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class ArgIsError{};
template
bool compair(const T&amp; t1,const T&amp; t2)
{
return t1&gt;t2;
}
template
bool IsMax(const vector&amp; v,int start,int end,const T&amp; t)throw (ArgIsError)
{
if(v.size()end)
throw ArgIsError();
int i;
for(i=start;i&lt;end;++i)
{
if(compair(v[i],t))
return false;
}
return true;
}
template
bool IsMin(const vector&amp; v,int start,int end,const T&amp; t)throw (ArgIsError)
{
if(v.size()end)
throw ArgIsError();
int i;
for(i=start;i&lt;end;++i)
{
if(!compair(v[i],t))
return false;
}
return true;
}
template
bool VerifySquenceOfBST(const vector&amp; sequence)
{
if(sequence.size()=0;--i)
{
if(sequence[i]&lt;sequence[length-1])
{
left=0;
right=i+1;
break;
}
}
try
{
if(!IsMax(sequence,left,right,sequence[length-1]) || !IsMin(sequence,right,length-1,sequence[length-1]))
{
return false;
}
}
catch(ArgIsError&amp;)
{
;
}
vector lseq(sequence.begin()+left,sequence.begin()+right),rseq(sequence.begin()+right,sequence.begin()+length-1);
if(VerifySquenceOfBST(lseq) &amp;&amp; VerifySquenceOfBST(rseq))
{
return true;
}
else
{
return false;
}
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往 <div>来自为知笔记(Wiz)</div>