题目描述
输入一个非空整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
//每次都找左右树的分界点，然后判断
bool judge(vector<int> sequence, int i_start, int i_end)
{
if (i_start-i_end>=0)
{
return true;
}
int i_root = sequence[i_end];
int index = i_start;
for (;index<i_end;index++)
{
//找到分界点，左侧数都小于根节点
if (sequence[index]>i_root)
{
break;
}
}
//判断右侧
for (int i_r_index=index;i_r_index<i_end;i_r_index++)
{
if (sequence[i_r_index]<i_root)
{
return false;
}
}
//再分别遍历左右子树判断
return judge(sequence, i_start, index-1) && judge(sequence, index, i_end - 1);
}
bool VerifySquenceOfBST(vector<int> sequence) {
if (sequence.size() == 0)
return false;
return judge(sequence, 0, sequence.size() - 1);
}
