输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
5
/ \
2 6
/ \
1 3
示例 1:
输入: [1,6,3,2,5]
输出: false
示例 2:
输入: [1,3,2,6,5]
输出: true
1 class Solution { 2 public boolean verifyPostorder(int[] postorder) { 3 if(postorder.length==0) 4 return true; 5 return process(postorder, 0, postorder.length-1); 6 7 } 8 public boolean process(int[] postorder,int i,int j) 9 { 10 if(i>=j) 11 return true; 12 //找到第一个比根节点大的位置下标p,划分出左右子树 13 int p = i; 14 while(postorder[p]<postorder[j]) 15 p++; 16 int m = p; 17 //左子树满足条件上面找p的时候已经验证过,下面验证右子树所有节点都要大于根 18 while(postorder[p]>postorder[j]) 19 p++; 20 //p!=j的话证明右子树中存在值比根大,违背条件 21 //同时需满足左子树,右子树也达标 22 return p==j && process(postorder,i,m-1) && process(postorder, m, j-1); 23 } 24 }