剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

 5
/ \

2 6 /
1 3

示例 1：

输入: [1,6,3,2,5]
输出: false
示例 2：

输入: [1,3,2,6,5]
输出: true

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

递归，后序遍历是左右中，所以根节点为 postorder[postorder.length - 1]，又因为二叉搜索树左 < 根 < 右，通过根节点的值将数组分为左右子树：
1. 左子树：start 到 root - 1
2. 右子树：root 到 end - 1 如果 start >= end - 1 证明已经递归完成左右子树，该数组是二叉搜索树的后序遍历。在比较大小时申明一指针 point，最终 point == end && 左子树成立 && 右子树成立即为最终结果。
迭代，将数组倒序后续遍历结果的左右中变为中右左，得出以下两种规律：
1. arr[i] < arr[i + 1]，那么 arr[i + 1] 必然是 arr[i] 的右子树
2. arr[i] > arr[i + 1]，那么 arr[i + 1] 必然是 arr[0] 到 arr[i] 之间某个节点的子节点，并且这个子节点的值一定是大于 arr[i + 1] 中最小的。由以上规律可使用单调栈（可恶又是单调栈-。-

代码

解法一

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    public boolean recur(int[] postorder, int start, int root) {
        if (start >= root - 1) return true;
        int point = start;
        while (postorder[point] < postorder[root]) point++;
        int middle = point;
        while (postorder[point] > postorder[root]) point++;
        return point == root && recur(postorder, start, middle - 1) && recur(postorder, middle, root - 1);
    }
}

解法二

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for (int i = postorder.length - 1; i >= 0; i--) {
            if (postorder[i] > root) return false;
            while (!stack.isEmpty() && stack.peek() > postorder[i])
                root = stack.pop();
            stack.add(postorder[i]);
        }
        return true;
    }
}

参考

思想原理：消除整个postorder，利用保证左子树或者右子树的正确性，来判断另外一侧。
1. 递归法，保证左子树正确（左子树均小于最右侧的root），此时判断右子树是不是均大于root。
2. 迭代法，倒叙遍历，此时为中右左，利用单调栈的while循环（栈顶大于遍历值），保证了右子树的正确，此时判断左子树是不是都小于root即可。
后续遍历结果是

[3,6,5,9,8,11,13,12,10]

从前往后不好看，我们来从后往前看

[10,12,13,11,8,9,5,6,3]

如果你仔细观察会发现一个规律，就是挨着的两个数如果arr[i]<arr[i+1]，那么arr[i+1]一定是arr[i]的右子节点，这一点是毋庸置疑的，我们可以看下上面的10和12是挨着的并且10<12，所以12是10的右子节点。同理12和13，8和9，5和6，他们都是挨着的，并且前面的都是小于后面的，所以后面的都是前面的右子节点。如果想证明也很简单，因为比arr[i]大的肯定都是他的右子节点，如果还是挨着他的，肯定是在后续遍历中所有的右子节点最后一个遍历的，所以他一定是arr[i]的右子节点。

我们刚才看的是升序的，再来看一下降序的（这里的升序和降序都是基于后续遍历从后往前看的，也就是上面蓝色数组）。如果arr[i]>arr[i+1]，那么arr[i+1]一定是arr[0]……arr[i]中某个节点的左子节点，并且这个值是大于arr[i+1]中最小的。我们来看一下上面的数组，比如13，11是降序的，那么11肯定是他前面某一个节点的左子节点，并且这个值是大于11中最小的，我们看到12和13都是大于11的，但12最小，所以11就是12的左子节点。同理我们可以观察到11和8是降序，8前面大于8中最小的是10，所以8就是10的左子节点。9和5是降序，6和3是降序，都遵守这个规律。

根据上面分析的过程，很容易想到使用栈来解决。遍历数组的所有元素，如果栈为空，就把当前元素压栈。如果栈不为空，并且当前元素大于栈顶元素，说明是升序的，那么就说明当前元素是栈顶元素的右子节点，就把当前元素压栈，如果一直升序，就一直压栈。当前元素小于栈顶元素，说明是倒序的，说明当前元素是某个节点的左子节点，我们目的是要找到这个左子节点的父节点，就让栈顶元素出栈，直到栈为空或者栈顶元素小于当前值为止，其中最后一个出栈的就是当前元素的父节点。

本文由 Meridian 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Mar 3,2022