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

2020-05-21 教育 97阅读
判断整数序列是不是二元查找树的后序遍历结果
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
8
/ \
6 10
/ \ / \
5 7 9 11 因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。
思路分析:
查找二叉树的特点就是左子树中的节点一定比根节点小,右子树中的节点一定比根节点大。OK,那用根节点就可以将数组分成两部分。步骤如下:
*从前往后遍历,找到第一个大于根节点的数。
*从这个数往后,判断是不是所有的在根节点以前的数都大于根节点,如果不是,那就不可能是查找二叉树的后序遍历结果。
*如果前面两个步骤都没问题,那就分别再判断左子树和右子树是否合法。
声明:你问我答网所有作品(图文、音视频)均由用户自行上传分享,仅供网友学习交流。若您的权利被侵害,请联系fangmu6661024@163.com