题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

---

思路：

解法一：递归

二叉搜索树，后序遍历的数组中，最后一位是根节点，保存根节点。

除根节点外，数组中分为两部分，前一部分全部小于根节点，为左子树，另一部分全部大于根节点，为右子树。

分别找出两部分的范围，对两个子树进行递归判断是否是后序遍历序列。

class Solution{public:  bool VerifySquenceOfBST(vector
       
         sequence)  {    if (sequence.empty())      return false;    return helper(sequence, 0, sequence.size() - 1);  }  bool helper(vector
        
          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 - 1) && helper(seq, i, end - 1);  }};
        
       

解法二：非递归

同样的，去除数组最后一个值，也就是根，数组分为左右子树两部分。

此时数组最右边的值是右子树的根节点，大于所有左子树的值。同时，右子树部分中，所有右子树元素都大于该值。

于是判断右子树是否符合条件即可。

class Solution{public:  bool VerifySquenceOfBST(vector
       
         sequence)  {    int j = sequence.size();    if (j == 0)      return false;    int i = 0;    while (--j)    {      while (sequence[i++] < sequence[j])        ;      while (sequence[i++] > sequence[j])        ;      if (i < j)        return false;      i = 0;    }    return true;  }};