前言

给出遍历的数组，不再有root节点，此时我们需要熟悉遍历的原理来合适的处理数组。

一、递归分治

1、思想

1）后续遍历为：左、右、根，所以注定数组的最后一个节点为root节点。（问题切入）
2）root的意义，将数组划分为左子树和右子树数组。
3）左右数组的意义，重复上面的划分。（递归过程）
4）直到只有数组只有一个节点的时候，此为递归出口。（递归出口）
5）左子树数组<root.val && 右子树数组>root.val，若不满足上述条件，则剪枝来结束递归分治。（剪枝条件）

2、源码

//剑指offer33.二叉搜索树的后序遍历序列int[] postorder;public boolean verifyPostorder(int[] postorder) {//后续遍历，左、右、根。this.postorder = postorder;return verify(0, postorder.length - 1);}public boolean verify(int left, int right) {if (left >= right)return true;int i = left;//左右根，最后的right节点为根节点。// 现在寻找小于根节点的为左子树while (postorder[i] < postorder[right])i++;//记录第一个大于根节点的index，这是右子树的开始。int r_begin = i;//判断找到的右子树所有的值是否都大于当前的根节点。while (postorder[i] > postorder[right])i++;//满足左子树值都小于当前根节点且右子树的值都大于当前根节点的值 && 划分的左子树也满足前面的条件 && 右子树也满足条件return i == right && verify(left, r_begin - 1) && verify(r_begin, right - 1);}

二、单调栈

1、思想

1）问题切入，将数组翻转得到新的遍历----逆前序遍历----右、左、根。
2）右斜树是一个递增的过程。
3）右节点递增入栈；每次拿到rootValue，判断左节点是否小于rootValue.

2、源码

//剑指offer33.二叉搜索树的后序遍历序列//画一棵满二叉搜索树，方便算法的理解。public boolean verifyPostorder2(int[] postorder) {//后续遍历，左、右、根。从数组倒着看，就是root right left,此时就变成了逆前序遍历。//设置开始时最大的根节点，所有遇到的左节点不大于它int rootValue = Integer.MAX_VALUE;//单掉栈思想，二叉搜索树的右斜树都是单掉递增的，而左孩子节点都是小于父节点root。Deque<Integer> cache = new LinkedList<Integer>();for(int i = postorder.length - 1;i>=0;i--){//下面的while代码是取到了rootValue,左边的树要小于根节点if(postorder[i] > rootValue)return false;while(!cache.isEmpty() && postorder[i] < cache.peek())//寻找根节点，记录根节点并出栈，因为这个根节点只能用于当前左子树的rootrootValue = cache.pop();//记录未来的根节点root,这对应着上面出栈的root，相当于更新root节点cache.push(postorder[i]);}//所有右节点都大于root，for中的if也决定了所有左节点小于根节点return true;}

总结

1）递归分治，一分为二，二分为四的递归下去。
2）单调栈，思想就是保持单调。