二叉搜索树的后序遍历序列
题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路挺清晰的,但是不知道为什么,提交了好几次都只能通过部分用例,最后修修改改才通过的。总感觉我的这个做法不太好。
首先,后序遍历的最后一个元素是树的根节点root,然后可以将整个序列分成两个部分,分别是root的左子树和右子树,左子树的所有元素都比root小,右子树的所有元素都比root大。按照这个思路,就可以用左右子树分别递归,最后判断是否满足条件了。
代码如下:
public boolean VerifySquenceOfBST(int [] sequence) { int leftRoot = 0, rightRoot = sequence.length-1; if (sequence.length == 0) return false; if (sequence.length <= 3) return true; //只有一个后序序列,当只有三个节点的时候只能返回true for (int i=0; i<sequence.length; i++) { //找到第一个比root大的元素的位置,确定左子树的范围 if (sequence[i] >= sequence[sequence.length-1]) { leftRoot = i; break; } } for (int i=leftRoot+1; i<sequence.length; i++) { //判断右子树的所有元素是否比root大 if (sequence[i] < sequence[sequence.length-1]) return false; } if (leftRoot >= rightRoot) return VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, leftRoot)); if (leftRoot == 0) return VerifySquenceOfBST(Arrays.copyOfRange(sequence, leftRoot, rightRoot)); return VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, leftRoot)) && VerifySquenceOfBST(Arrays.copyOfRange(sequence, leftRoot, rightRoot)); }
相关推荐
darlingtangli 2019-06-27
BitTigerio 2018-04-19
baike 2020-05-09
choupiaoyi 2020-02-01
mieleizhi0 2019-12-31
郭岚 2019-11-04
徐建岗网络管理 2019-11-02
Cypress 2019-07-01
YUAN 2019-06-28
WindChaser 2019-06-21
xingweiyong 2015-04-07
王少雷的黑马 2017-02-17
zhglinux 2018-07-27
龙源潇俊 2018-05-08
梦呓bolg 2017-12-12
tansuo 2015-08-30
wangxiaohua 2015-08-11
LeonTom 2017-06-02
electricperi 2015-02-15
tansuo 2015-01-12
大数据分析BDA 2014-08-02
tansuo 2014-07-30
cl00abc 2014-02-07
云华00 2013-11-10
pythoncream 2018-12-24
guyuanxiang 2014-04-29
妖怪哪里跑 2019-02-21
PHP100 2019-03-28
BitTigerio 2018-03-30