《剑指Offer》Java刷题 NO.23 二叉树的后序遍历序列
《剑指Offer》Java刷题 NO.23 二叉树的后序遍历序列(二叉搜索树、后序遍历、二分查找、递归)
时间：2020-02-29 题目： 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路： 先明确什么是二叉搜索树： 根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值，这一规则适用于二叉搜索树中的每一个节点；也就是说左子树的所有值<根结点的值<右子树的所有值，适用于所有的子树。例如下图： 后序遍历输出应该为：3 4 9 5 12 11 10
- 既然所有的子树都要满足以上规则，那么递归方法是很合适的，观察可以发现树的根结点放在数组的最右端
-
从头开始找到第一个大于根结点的结点作为分界 然后判断当前节点开始到倒数第二个结点，如果有结点的值比根节点的值小的话，就返回false，否则就继续递归判断左子树和右子树是否同时为true 递归的结束条件是入参子数组的长度<=2，此时应该直接返回true，两个元素，例如上图的[3,4]子树，不论顺序是[3,4]还是[4,3]都可以被认为是后序遍历； 另外，当子数组长度为3时，不用再进行对左右子树的递归了，直接在循环判断结束之后返回结果就行了，因为此时左右子树都只有一个元素。
- 大神写的一个非递归程序，虽然复杂度有点高，是O(n²)，但是思路很好 因为右子树的根节点的值依旧大于上一层的左子树和本身的左子树，所以每次把size减一，从右向左判断每一个结点对应的剩余子树节点顺序是不是符合规则； 判断规则为从第一个结点开始找到第一个大于根结点（当前最后元素）的结点，然后继续从当前结点往后找直到结点的值不大于根结点，判断是否正好到了倒数第二个结点，如果不是就返回false
Java代码：
/**
* 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。
* 假设输入的数组的任意两个数字都互不相同。
*/
public class VerifySequenceOfBST {
public static boolean verifySequenceOfBST1(int[] sequence){
if(sequence.length == 0) return false;
return judge(sequence,0,sequence.length-1);
}
public static boolean judge(int[] arr,int start,int root){
int length = root-start+1;
if(length <= 2) return true;
int i = 0;
for(;i < root;i++){
if(arr[i] > arr[root]) break;
}
int j=i-1;
for(;i < root;i++){
if(arr[i] < arr[root]) return false;
}
if(length==3) return true;
return judge(arr,start,j)&&judge(arr,j+1,root-1);
}
/**
*非递归解法
*/
public static boolean verifySequenceOfBST2(int[] sequence){
int size=sequence.length;
if(size==0) return false;
if(size<=2) return true;
while(--size>=0){
int i=0;
while (sequence[i]<sequence[size]) i++;
while (sequence[i]>sequence[size]) i++;
if(i!=size) return false;
}
return true;
}
public static void main(String[] args) {
int[] test0={
1};
int[] test1={
3,4};
int[] test2={
1,2,3};
int[] test3={
1,3,2};
int[] test4={
3,8,5,11,14,13,10};
System.out.println(verifySequenceOfBST2(test1));
}
}
