📃 题目描述

题目链接：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

注意:你可以假设树中没有重复的元素。

例如，给出

• 中序遍历 inorder = [9,3,15,20,7]
• 后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

🔔 解题思路

中序遍历：左根右，后序遍历：左右根

根据后序遍历的最后一个节点，在中序遍历中找到根节点的位置，然后就可以划分左右子树了

需要注意的细节就是下标的选取要控制好，左闭右开还是左开右闭还是左闭右闭？这里我选择的是左闭右开

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree1(inorder, 0, inorder.length,
                          postorder, 0, postorder.length);
    }

    /**
     * @param inorder (左闭右开)
     * @param inLeft inorder 数组的起始下标
     * @param inRight inorder 数组的终止下标
     * @param postorder (左闭右开)
     * @param postLeft postorder 数组的起始下标
     * @param postRight postorder 数组的终止下标
     * @return
     */
    private TreeNode buildTree1(int[] inorder, int inLeft, int inRight,
                                int[] postorder, int postLeft, int postRight) {
        // 只有一个元素
        if (inLeft + 1 == inRight) {
            return new TreeNode(inorder[inLeft]);
        }
        // 没有元素
        if (inLeft + 1 > inRight) {
            return null;
        }

        // 后序数组的最后一个节点为根节点
        TreeNode root = new TreeNode(postorder[postRight - 1]);
        // 在中序数组中找到根节点的位置
        int index = inLeft;
        for (; index < inRight; index ++) {
            if (inorder[index] == root.val) {
                break;
            }
        }

        // 构建左子树
        root.left = buildTree1(inorder, inLeft, index,
                               postorder, postLeft, postLeft + (index - inLeft));
        // 构建右子树
        root.right = buildTree1(inorder, index + 1, inRight,
                                postorder, postLeft + (index - inLeft), postRight - 1);

        return root;

    }
}

💥 复杂度分析

• 空间复杂度：O(LogN)
• 时间复杂度：O(N)