题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
题目链接：牛客网
解题思路
public class Main {
public static void main(String
[] args
) {
int[] data
= {4, 8, 6, 12, 16, 14, 10};
System
.out
.println("true: " + verifySquenceOfBST(data
));
int[] data2
= {7, 4, 6, 5};
System
.out
.println("false: " + verifySquenceOfBST(data2
));
}
public static boolean verifySquenceOfBST(int[] sequence
) {
if (sequence
== null
|| sequence
.length
== 0) {
return false;
}
return verify(sequence
,0,sequence
.length
- 1);
}
public static boolean verify(int[] sequence
,int first
,int last
) {
if (last
- first
<= 1) {
return true;
}
int rootVal
= sequence
[last
];
int cutIndex
= first
;
while (cutIndex
< last
&& sequence
[cutIndex
] <= rootVal
) {
cutIndex
++;
}
for (int i
= cutIndex
;i
< last
;i
++) {
if (sequence
[i
] < rootVal
) {
return false;
}
}
return verify(sequence
,first
,cutIndex
- 1) && verify(sequence
,cutIndex
,last
- 1);
}
}
测试结果
