23 图解剑指Offer 二叉搜索树的后序遍历序列 Java题解

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

题解:

（1)已知二叉搜索树的后序遍历序列，由于二叉搜索树left<root<right, 所以 int[] arr = seq.clone(); Arrays.sort(arr);将后序序列按照从小到大排序即可得到二叉搜索树的中序序列。 (2) 如果后序序列是中序列的栈弹出序列即可验证，后序序列是该二叉搜索树的后序序列。 (3) 所以先获得二叉搜索树的中序序列，然后在调用之前写的判断栈的弹出序列方法，返回该方法的值。

图解:

代码:

import java.util.Stack;
import java.util.Arrays;
 
public class Solution {
          
   
    public boolean VerifySquenceOfBST(int [] seq) {
          
   
        int[] arr = seq.clone();
        Arrays.sort(arr);
        return IsPopOrder(arr,seq);
    }
     
//判断第二个序列是否可能为第一个序列的弹出顺序,引用的“栈的压入、弹出序列”题目的答案
public boolean IsPopOrder(int [] pushA,int [] popA) {
          
   
        if(pushA.length == 0 || popA.length == 0)
            return false;
        Stack<Integer> s = new Stack<Integer>();
        //用于标识弹出序列的位置
        int popIndex = 0;
        for(int i = 0; i< pushA.length;i++){
          
   
            s.push(pushA[i]);
            //如果栈不为空，且栈顶元素等于弹出序列
            while(!s.empty() &&s.peek() == popA[popIndex]){
          
   
                //出栈
                s.pop();
                //弹出序列向后一位
                popIndex++;
            }
        }
        return s.empty();
    }
}

复杂度

空间复杂度: 空间复杂度为O(n) 和 二叉树节点个数有关。 最坏时间复杂度: 时间复杂度 for循环 while循环:O(n2)