Ex33 二叉搜索树的后序遍历序列

题目描述

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

解题思路

后序遍历的特点就是：根结点在最后面遍历。所以，比根结点（也就是后序遍历序列的最后一个节点）小的是左子树，比根结点大的就是右子树。根据以上的分析，检查大小关系，然后递归的分析左子树，右子树……等等。

代码

bool
verifyPostorder (int *postorder, int postorderSize)
{
  if (!postorder || postorderSize <= 0)
    return true;
  int root_value = postorder[postorderSize - 1];
  int index = -1;
  for (int i = 0; i < postorderSize - 1; ++i)
    {
      if (postorder[i] > root_value)
        {
          index = i;
          break;
        }
    }
  if (index == -1)
    index = postorderSize - 1;
  for (int i = index + 1; i < postorderSize - 1; ++i)
    {
      if (postorder[i] < root_value)
        return false;
    }
  return verifyPostorder (postorder, index)
         && verifyPostorder (postorder + index, postorderSize - 1 - index);
}

结果

执行结果：通过

执行用时：0 ms, 在所有 C 提交中击败了100.00%的用户

内存消耗：5.9 MB, 在所有 C 提交中击败了5.24%的用户