题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
提示：
数组长度 <= 1000

解法1：非递归，栈+倒序后序遍历，时间复杂度o(n)，空间复杂度o(n)

  1. 给定的后序序列改为倒序，将遍历从 left -> right -> root改为 root ->right ->left
  2. 每次在最后将当前元素入栈，按照root -> right ->left的顺序执行
  3. 栈不为空且当前元素小于栈顶元素时，说明到了左子树，那么把右子树元素全部出栈，最后一个出栈的元素就是根节点，记录其值root_val
  4. 左子树遍历时，如果有任意值大于root_val直接返回false
    1. class Solution {
    2.  public boolean verifyPostorder(int[] postorder) {
    3.      // 采用跟后序遍历相反的顺序，左右根->根右左
    4.      Deque<Integer> deque = new LinkedList<>();
    5.      int root_val = Integer.MAX_VALUE;// 左子树的元素一定比当前节点元素值小
    6.      for(int i = postorder.length - 1 ; i >= 0 ;i--){
    7.          // 当前节点的值小于栈顶指针，说明到了左子树
    8.          while(!deque.isEmpty() && postorder[i] < deque.peek()){
    9.              root_val = deque.pop();
    10.          }
    11.          // 前一个节点左子树的值比该节点值大的话
    12.          if(postorder[i] > root_val)
    13.              return false;
    14.          // 加入当前节点
    15.          deque.push(postorder[i]);
    16.      }
    17.      return true;
    18.  }
    19. }

    解法2：递归分治，时间复杂度o(n^2)，空间复杂度o(n)

  • 结束条件i >= j ，则返回true，说明区间缩小到1了；
  • 分治条件：分为左子树和右子树，每次找到其中的根节点，使用遍历指针p
    • 根据二叉搜索树和后续遍历的性质，每次从i开始遍历（左子树第一个节点），第一个比nums[j]大的就是右子树的第一个右节点（后续遍历为左右根，第一个比根大的节点），记录下标m，m-1就是根节点
    • 找到右子树的末尾，从根节点开始一直找，找到第一个比根节点小的前一个节点即可
    • 左右子区间递归：i - 1到m - 1，m 到j - 1

  • 返回条件：如果是后续遍历，p应该等于j，并且满足最后的递归结果，两者相与；否则返回false

    1. class Solution {
    2.   public boolean verifyPostorder(int[] postorder) {
    3.       return help(postorder,0,postorder.length - 1);
    4.   }
    6.   public boolean help(int[]postorder,int i ,int j){
    7.       // 满足区间逼近
    8.       if(i >= j)
    9.           return true;
    10.       // 记录左子树的起始节点
    11.       int p = i;
    12.       while(postorder[p] < postorder[j]) p++;
    13.       // 找到（第一个右节点），m-1就是根节点
    14.       int m = p;
    15.       // 回到根节点
    16.       while(postorder[p] > postorder[j]) p++;
    17.       // 遍历指针应该到j的位置(回到根节点) && 满足左右区间递归i,m-1和m到j-1
    18.       return p == j && help(postorder,i,r - 1) && help(postorder,r , j - 1);
    19.   }
    20. }