题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路
- 二叉搜索树满足根节点的值大于左孩子并且小于右孩子。
- 二叉树的后序遍历顺序是:左->右->根,所以序列的最后一位是根节点的值。
- 递归处理后序遍历的数组,每次都找到根节点(最后一个元素),左右孩子的分界点。
- 若left>=right,说明序列没问题,结束递归。
Java代码实现
public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence.length == 0) return false; return VerifySquenceOfBST(sequence,0,sequence.length-1); } private boolean VerifySquenceOfBST(int [] sequence,int left,int right){ if(left >= right){ return true; } int rootVal = sequence[right]; int mid = right-1; //寻找分界点 while (mid >=left) { if(sequence[mid]<rootVal){ break; } mid--; } for (int i = left; i <= mid; i++) { if(sequence[i] > rootVal){ return false; } } return VerifySquenceOfBST(sequence,left,mid)&&VerifySquenceOfBST(sequence,mid+1,right-1); } }