二叉搜索树的后序遍历序列

2020-12-19

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

难度中等243收藏分享切换为英文接收动态反馈

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

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

示例 1：

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

示例 2：

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

提示：

数组长度 <= 1000

递归判断

小于根节点的值都在左子树上，大于根节点的值都在右子树上，所以从头开始遍历，找到最后一个不大于根节点的值的index，这个index将后序遍历的所有数字划分为两拨，左边的是左子树上的值，右边的是右子树上的值，然后递归的分割每个子树。
注意：判断条件是如果遍历左子树的值的数量+右子树的值的数量的值等于当前递归的end - start，那么是成立的，否则是不成立的。

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, int i, int j) {
        if(i >= j) return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        while(postorder[p] > postorder[j]) p++;
        // 当p==j时说明左子树和右子树都满足条件，否则就是不满足条件
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}

二叉搜索树的中序遍历结果是有序的，通过后序遍历序列可以得出二叉搜索树的中序遍历结果

通过后序遍历结果和中序遍历结果我们可以获取每个子树的根节点的index和左右子树的节点的数量，然后递归的去检查要查找的根节点的位置是不是在中序遍历的子树的startIndex和endIndex的区间之内，如果不在区间之内，那么这棵树就不是二叉搜索树

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        int[] inorder = new int[postorder.length];
        for (int i = 0; i < postorder.length; i++) {
            inorder[i] = postorder[i];
        }
        Arrays.sort(inorder);//二叉搜索树的中序遍历结果是有序的，通过后序遍历序列可以得出二叉搜索树的中序遍历结果

        Map<Integer, Integer> inorderIndexMap = new HashMap<>();//将中序遍历结果加入哈希表中，进行值和index映射，以快速查找
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }

        return deepVerify(postorder, 0, postorder.length - 1,
                inorder, 0, inorder.length - 1, inorderIndexMap);
    }

    public boolean deepVerify(int[] postorder, int postoderStart, int postorderEnd,
                                     int[] inorder, int inorderStart, int inorderEnd,
                                     Map<Integer, Integer> inorderIndexMap) {
        if (postoderStart > postorderEnd) {
            return true;
        } else {
            int root = postorder[postorderEnd];//后序遍历里最后一个元素是根节点

            if (postoderStart == postorderEnd) {
                if (postorder[postorderEnd] == inorder[inorderStart]) {//如果数组中只有一个元素了，那么该元素在中序遍历和后序遍历中应该相同（因为每次中序遍历和后序遍历的开始和结束index是设置好对应的）
                    return true;
                } else {
                    return false;
                }
            } else {
                int rootIndex = inorderIndexMap.get(root);//获取该根节点在中序遍历中的index，以此计算左子树和右子树的节点的个数
                if (rootIndex < inorderStart || rootIndex > inorderEnd) {//区间里没有这个值，因此不符合要求
                    return false;
                }
                int leftNodeNum = rootIndex - inorderStart;//左子树节点的数量
                int rightNodeNum = inorderEnd - rootIndex;//右子树节点的数量
                //验证左子树和右子树
                return deepVerify(postorder, postoderStart, postoderStart + leftNodeNum - 1,
                        inorder, inorderStart, rootIndex - 1, inorderIndexMap) &&
                        deepVerify(postorder, postorderEnd-rightNodeNum, postorderEnd - 1,
                                inorder, rootIndex + 1, inorderEnd, inorderIndexMap);
            }
        }
    }
}

时间复杂度O(nlog(n))，主要是在排序

空间复杂度O(n)中序的序列和哈希表

不使用辅助空间

在二叉搜索树中，如果某个节点的值小于根节点，那么该节点的值一定在左子树中，如果某个节点的值大于根节点，那么该节点的值一定在右子树中
在后序遍历中，最后一个节点一定是根节点，而其前面的节点，一定在某个index处分为左子树和右子树，只需遍历后序遍历的序列，找到第一个不小于根节点的节点，就是右子树的第一个节点，判断右子树中的每个节点是否都大于根节点，如果不满足大于根节点的要求，那么这棵树就不是二叉搜索树，然后再递归的验证左子树和右子树

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return deepVerify(postorder, 0, postorder.length - 1);
    }
    public boolean deepVerify(int[] postorder, int start, int end) {
        if (end - start <= 0) return true;

        int root = postorder[end];
        int index = start;
        for (; index < end; index++) {//如果某个节点的值大于root，在二叉搜索树中，这个节点一定在右子树中
            if (postorder[index] > root) {
                break;
            }
        }
        for (int i = index; i < end; i++) {//判断右子树中的节点的值是不是都大于根节点，如果不是，那么不符合条件
            if (postorder[i] < root) {
                return false;
            }
        }
        //递归的判断左子树和右子树
        return deepVerify(postorder, start, index - 1) && deepVerify(postorder, index, end - 1);
    }
}