【剑指offer】二叉搜索树的后序遍历

题目描述

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

思路

首先判断数组是否为空，为空就返回false，如果数组为1，就相当于只有一个根节点，那么就直接返回true。如果数组中前面的数小于数组的最后一个数（根），那么前面的那些小于根的数就为根的左子树，剩下的就为右子树，然后再分别对最字数和右子树进行递归。

public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence.length == 0){ return false; } return preOrder(sequence,0,sequence.length-1); } public boolean preOrder(int[] a,int start,int end){ if(start>=end){ return true; } int i = start; for(;i<end;i++){ if(a[i]>a[end]){ break; } } for(int j = i;j<end;j++){ if(a[j]<a[end]){ return false; } } return preOrder(a,start,i-1)&&preOrder(a,i,end-1); } }