根据一棵树的后序遍历与中序遍历构造二叉树

前言

今天的文章是上一篇的后续 https://www.jianshu.com/p/ad76788c1de1 有兴趣可以往前翻阅一下

//根据一棵树的中序遍历与后序遍历构造二叉树。 
//
// 注意: 
//你可以假设树中没有重复的元素。 
//
// 例如，给出 
//
// 中序遍历 inorder = [9,3,15,20,7]
//后序遍历 postorder = [9,15,7,20,3] 
//
// 返回如下的二叉树： 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7
// 

首先分析一下后序和中序遍历的特点

1、后序遍历中，最后一个遍历结果是二叉树的根节点；
2、中序遍历中，根节点的左侧遍历结果是二叉树的左子树，根节点右侧遍历结果是二叉树的右子树。

惯例还是用例题进行验证
那么我们用例题来做一下验证

后序遍历结果：[9,15,7,20,3] ，遍历最后一个元素是3，是二叉树的根节点；
中序遍历结果：[9,3,15,20,7] ，3的左边[9]，是二叉树的左子树，[15,20,7]是二叉树的右子树。

此题的解法和用前序和中序构建二叉树雷同：

1、找到二叉树的根节点rootNode(eg：3)
2、找到rootNode在中序遍历中的位置（eg：3的下表是1）
3、找到左子树前序和中序遍历结果区间(eg：左子树前序：[9]，左子树中序：[9])
4、找到右子树前序和中序遍历结果区间(eg：左右树前序：[20,15,7]，左子树中序：[15,20,7])
5、构建二叉树并返回。

直接上代码

private Map<Integer, Integer> inorderValue2IndexMap = new HashMap();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int size = postorder.length;
        for (int i = inorder.length - 1; i >= 0; i--) {
            // 将中序遍历结果的值和index建立映射关系，方便寻找各节点中序下标
            inorderValue2IndexMap.put(inorder[i], i);
        }
        return buildTree(postorder, inorder, 0, size - 1, 0, size - 1);
    }

    private TreeNode buildTree(int[] postorder, int[] inorder, int postorderStart, int postorderEnd, int inorderStart, int inorderEnd) {
        // 1 判断是否没有左子树或右子树
        if (postorderEnd < postorderStart) {
            return null;
        }
        // 2 构造当前节点，后序遍历区间最后一个值就是当前节点的值
        int rootValue = postorder[postorderEnd];
        TreeNode rootNode = new TreeNode(rootValue);
        // 3 找到左子树区间 构建左子树
        int inorderIndex = inorderValue2IndexMap.get(rootValue);
        int rightCount = inorderEnd - inorderIndex;
        TreeNode leftNode = buildTree(postorder, inorder, postorderStart, postorderEnd-rightCount -1, inorderStart, inorderIndex - 1);
        rootNode.left = leftNode;
        // 4 找到右子树区间 构建右子树
        TreeNode rightNode = buildTree(postorder, inorder, postorderEnd-rightCount, postorderEnd - 1, inorderIndex + 1, inorderEnd);
        rootNode.right = rightNode;
        // 5 返回
        return rootNode;
    }