判断该数组是不是某二叉查找树(折半查找树)的后序遍历的结果。

Question

【问题描述】输入一个整数数组，判断该数组是不是某二叉查找树(折半查找树)的后序遍历的结果。如果是返回true，否则返回false。
【输入形式】输入任意长度的数组，数字之间空格分开
【输出形式】true 或者 false
【样例输入】输入5 7 6 9 11 10 8
【样例输出】true
【样例说明】由于这一整数序列是如下树的后序遍历结果：

      8
   /      \
  6      10
/   \     /   \

5 7 9 11

因此返回true。

【评分标准】暴力求解法不得分。

【提示】后序遍历的最后一个结点一定是根结点，那么前面的数据就可以划分为比根小的、比根大的。依此类推下去。

我的思路是数组长度len除以二得到ret，则0到ret左闭右开区间内是左子树，ret到len左闭右开区间内是右子树，递归定义，得到判断的函数，这个思路是正确的吗？我的递归学的不是很好，如果是正确的能烦请您帮我实现吗？

Answer 1

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7662275
• 除此之外, 这篇博客: C语言实现八大排序算法详解及其性能之间的中的 名字已经暴露了他的算法，就是往里面插入数据，就拿我们生活中的例子来说，打扑克牌。我们往手里码牌的时候，是一张一张的码，先码一张，抓手心，不需要修改位置，因为只有一张牌，一定是有序的。再接一张，和手里的牌对比大小，调整位置，选择放在它的左边或者右边。然后接着码，又接到一张牌，拿到先和右边的牌比，比右边还大就放到最右边，如果比右边这张小呢，在和左边这张比。同样，我们这里也是这样的，首先我们默认第一个元素，一定是有序，OK吧。然后第二个，元素比较，大，放到左边，小放到右边。然后第三个元素，直到第N个，比它前一个大，继续往前找位置，直到找到对应位置了，就是有序数列了。（当然每次找位置都是在一个有序的序列中找，所以完全可以用二分查找找位置，数据大的话，二分明显快于我们一张一张比） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 算法思想