面试100题系列之12判断序列是不是查找二叉树的后

面试100题系列之12判断序列是不是查找二叉树的后

判断整数序列是不是二元查找树的后序遍历结果
输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
8
/ \
6 10
/ \ / \
5 7 9 11 因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
思路分析：
查找二叉树的特点就是左子树中的节点一定比根节点小，右子树中的节点一定比根节点大。OK，那用根节点就可以将数组分成两部分。步骤如下：
*从前往后遍历，找到第一个大于根节点的数。
*从这个数往后，判断是不是所有的在根节点以前的数都大于根节点，如果不是，那就不可能是查找二叉树的后序遍历结果。
*如果前面两个步骤都没问题，那就分别再判断左子树和右子树是否合法。

100万节点 lg1000000/lg2=19.9 也就是 2^19<1000000<2^20 所以 二叉树共计有20层 最差的情况 就是执行20次查找。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息