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

in with 0 comment

剑指 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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

  1. 递归,后序遍历是左右中,所以根节点为 postorder[postorder.length - 1],又因为二叉搜索树 左 < 根 < 右,通过根节点的值将数组分为左右子树:

    1. 左子树:start 到 root - 1
    2. 右子树:root 到 end - 1 如果 start >= end - 1 证明已经递归完成左右子树,该数组是二叉搜索树的后序遍历。在比较大小时申明一指针 point,最终 point == end && 左子树成立 && 右子树成立即为最终结果。
  2. 迭代,将数组倒序后续遍历结果的左右中变为中右左,得出以下两种规律:

    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;
    }
}

参考

  1. 思想原理:消除整个postorder,利用保证左子树或者右子树的正确性,来判断另外一侧。

    1. 递归法,保证左子树正确(左子树均小于最右侧的root),此时判断右子树是不是均大于root。
    2. 迭代法,倒叙遍历,此时为中右左,利用单调栈的while循环(栈顶大于遍历值),保证了右子树的正确,此时判断左子树是不是都小于root即可。
  2. 后续遍历结果是

[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是降序,都遵守这个规律。

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