二叉搜索树，左子树的值小于根节点 右子树的值大于根节点。 * 后续遍历 ：左右根
package new_offer; /** * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 * 二叉搜索树，左子树的值小于根节点 右子树的值大于根节点。 * 后续遍历 ：左右根 * @author Sonya * */ public class N23_VerifySquenceOfBST { public boolean VerifySquenceOfBST(int [] sequence) { int len=sequence.length; return VerifySquenceOfBST2(sequence,len); } //需要使用递归 public boolean VerifySquenceOfBST2(int [] seq,int len) { //判断是否为空 if(len<=0) return false; int root=seq[len-1];//找到根节点 //找到左子树 int i=0; for(;i<len-1;i++) { if(seq[i]>root) break; } //int j=len-i-1; //在二叉搜索树种右节点比根大 int j=i; for(;j<len-1;j++) { if(seq[j]<root) return false; } //判断左子树是否是后续二叉搜索树 boolean left=true; if(i>0) {left=VerifySquenceOfBST2(seq,i);} //判断右子树是否是后续二叉搜索树 boolean right=true; if(i<len-1) { int seq2[]=java.util.Arrays.copyOfRange(seq, i, len-1); right=VerifySquenceOfBST2(seq2,len-i-1);} return left&&right; } public static void main(String[] args) { // TODO Auto-generated method stub } }
转载于:https://www.cnblogs.com/kexiblog/p/11126380.html
