本文主要是介绍【转载】判断整数序列是不是二元查找树的后序遍历结果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
判断整数序列是不是二元查找树的后序遍历结果题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
ANSWER:
This is an interesting one. There is a traditional question that requires the binary tree to be re-constructed from mid/post/pre order results. This seems similar. For the problems related to (binary) trees, recursion is the first choice.
In this problem, we know in post-order results, the last number should be the root. So we have known the root of the BST is 8 in the example. So we can split the array by the root.
int isPostorderResult(int a[], int n) {return helper(a, 0, n-1);
}
int helper(int a[], int s, int e) {if (e==s) return 1;int i=e-1;while (a[e]>a[i] && i>=s) i--;if (!helper(a, i+1, e-1))return 0;int k = i;while (i>=s && a[e]<a[i]) i--; if (i < s)return helper(a, s, k);elsereturn 0;
}
Maybe another solution is also fine:
int helper(int a[], int s, int e, int max, int min) Similar to http://blog.csdn.net/taoqick/article/details/16992475
这篇关于【转载】判断整数序列是不是二元查找树的后序遍历结果的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
