剑指offer 面试题33 二叉搜索树的后序遍历序列
二叉搜索树的后序遍历序列
题目
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路
在后序遍历得到的序列中,最后一个数字是树的根节点的值。数组中前面的数字可以分为两部分:一部分是左子树节点的值,它们都比根节点的值小;第二部分是右子树节点的值,它们都比根节点的值大。
代码
public boolean VerifySequenceOfBST(int sequence[], int start,int end){ if(sequence == null || sequence.length <=0){ return false; } int root= sequence[end]; //在二叉搜索树中左子树节点的值小于根节点的值 int i=start; for(;i<end;i++) { if(sequence[i]>root) break; } //在二叉搜索树中右子树节点的值大于根节点的值 int j = i; for(;j<end;j++) { if(sequence[j]<root) return false; } //判断左子树是不是二叉搜索树 boolean left = true; if(i>start) left=VerifySequenceOfBST(sequence, start,i-1); //判断右子树是不是二叉搜索树 bool right = true; if(i<end) right=VerifySequenceOfBST(sequence,i, end-i); return(left&&right); }
下一篇:
【蓝桥杯-寻找三位数】