题目
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路 + 代码
二叉搜索树的左子树所有节点小于根节点,右子树的所有节点大于根节点。
后序遍历是先访问左子树,后访问右子树。
因此,根节点永远在序列的最后位置。找到根节点数值后,根据前面节点数值与根节点的大小关系,找到左右子树的分割位置,递归求解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence==null || sequence.length==0) return false; return VerifySquenceOfBST(sequence, 0, sequence.length-1); } private boolean VerifySquenceOfBST(int[] sequence, int start, int end){ if(start >= end) return true; int currentCutIndex = start; while(sequence[currentCutIndex]<sequence[end]){ currentCutIndex++; } for(int i=currentCutIndex; i<end; i++){ if(sequence[i]<sequence[end]) return false; } return VerifySquenceOfBST(sequence, start, currentCutIndex-1) && VerifySquenceOfBST(sequence, currentCutIndex, end-1); } }
|