题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路：
解法一：递归
二叉搜索树，后序遍历的数组中，最后一位是根节点，保存根节点。
除根节点外，数组中分为两部分，前一部分全部小于根节点，为左子树，另一部分全部大于根节点，为右子树。
分别找出两部分的范围，对两个子树进行递归判断是否是后序遍历序列。
class Solution
{
public:
bool VerifySquenceOfBST(vector<int> sequence)
{
if (sequence.empty())
return false;
return helper(sequence, , sequence.size() - );
}
bool helper(vector<int> seq, int beg, int end)
{
if (beg >=end)
return true;
int root = seq[end];
int i = beg;
while (seq[i] < root)
{
i++;
}
int j = i;
while (j < end)
{
if (seq[j] < root)
{
return false;
}
j++;
}
return helper(seq, beg, i - ) && helper(seq, i, end - );
}
};
解法二：非递归
同样的，去除数组最后一个值，也就是根，数组分为左右子树两部分。
此时数组最右边的值是右子树的根节点，大于所有左子树的值。同时，右子树部分中，所有右子树元素都大于该值。
于是判断右子树是否符合条件即可。
class Solution
{
public:
bool VerifySquenceOfBST(vector<int> sequence)
{
int j = sequence.size();
if (j == )
return false; int i = ;
while (--j)
{
while (sequence[i++] < sequence[j])
;
while (sequence[i++] > sequence[j])
; if (i < j)
return false;
i = ;
}
return true;
}
};