7.22 第一次做，无法 AC
7.23 无法 AC
7.25 无法 AC
7.28 可以 AC

题目描述

原题链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

解题思路

K 神题解：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/

  • 递归得用到左右边界，题目所给方法只有一个数组，所以得自己重新写一个递归方法！

  • 题目所给的二叉树搜索树的后序遍历序列数组，那数组的最后一个值肯定就是根节点！

7.23 感悟：

  • 这道题不用重新建造一颗二叉树！
  • 相反，只需要比大小就可以确定是不是二叉树，因为题目给的是二叉搜索树！

  • 所以这道题的核心是能否正确比大小！

  • 由于是二叉搜索树的后序遍历序列，所以原后序遍历数组的最后一个数必定是根节点，我们此时要做的就是遍历原数组，找到第一个比该根节点大的数，此数就是原数组能构建的二叉树的根节点的右子树的第一个节点，从此节点开始继续往后遍历直到遇到在数组最后的根节点，如果遍历到最后的数都比根节点大，那么原数组的比大小关系就满足二叉搜索树的后序遍历序列的要求！

  • 但仅凭原数组构成的二叉树满足是不够的，还得判断原数组构成的二叉树的左右子树们满不满足，所以要递归判断左右子树们的大小关系是否也能满足二叉搜索树后序遍历序列的大小要求。

  • 遍历是需要传入的参数是：原数组、左边界和右边界。

  • 不管是遍历左子树还是遍历右子树，传入原数组肯定不会错，因为我们还传入了想要遍历的左右边界，这样就不会担心数据少了或多了。

  • 至于如果要快速得出要遍历的数组的左右边界，在第一次遍历原数组时找到的第一个比根节点大的数的索引要记录下来，其左边就是左子树，右边去掉最后一个数就是右子树，非常容易据其进行递归操作！

    1. class Solution {
    2.   public boolean verifyPostorder(int[] postorder) {
    3.       if(postorder.length == 0) return true;
    4.       // 传入原数组，原数组左边界，原数组右边界
    5.       return recur(postorder, 0, postorder.length - 1);
    6.   }
    8.   public boolean recur(int[] postorder, Integer left, Integer right) {
    9.       // 一直遍历到越过叶节点还没提前退出，说明前面的步骤都正确，返回 true
    10.       if(left >= right) return true;
    12.       // 二叉搜索树后序遍历的最后一个数就是根节点
    13.       // 从左到右找到第一个比根节点大的数，该节点就是右子树的第一个数
    14.       int i = left; // 从左边界开始遍历当前左右边界的数组
    15.       while(postorder[i] < postorder[right]) i++;
    16.       int m = i; // 记录下来以便用来递归左右子树时判断边界
    17.       while(postorder[i] > postorder[right]) i++;
    18.       // 如果 i 一直递增到与右边界相等，说明右子树的每一个数都比根节点大，符合二叉搜索树后序遍历要求，但是还得遍历看看左右子树符不符合要求！
    19.       return i == right && recur(postorder, left, m - 1) && recur(postorder, m, right - 1);
    20.   }
    21. }