二叉搜索树的后序遍历序列
题目描述
题目描述
输入一个整数数组,判断该数组是否是某个二叉搜索树的后序遍历结果
eg. {5,7,6,9,11,10,8} 8为根节点,将数组分成两部分,左部分都小于8, 右部分都大于8。每部分最后一个节点为根节点,依次判断。
bool
VerifySquenceOfBST(int sequence
[], int length
)
{
if(sequence
== nullptr
|| length
<=0)
return false
;
int root
= sequence
[length
-1];
int i
=0;
for(; i
<length
-1; i
++)
{
if(sequence
[i
] >root
)
break;
}
int j
=i
;
for(; j
<length
-1; j
++)
{
if(sequence
[j
] <root
)
return false
;
}
bool left
= true
;
if(i
>0)
left
= VerifySquenceOfBST(sequence
, i
);
bool right
= true
;
if(i
<length
-1)
right
= VerigySquenceOfBST(sequence
+i
, length
-i
-1);
return left
&& right
;
}