106. 从中序与后序遍历序列构造二叉树

题目

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

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

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

方法（递归）

二叉树的三种遍历次序依次为：

• 前序遍历：根、左、右
• 中序遍历：左、根、右
• 后序遍历：左、右、根

一个二叉树的前序、中序、后序遍历序列可以看作由如下部分构成：

• 前序遍历序列：

    [根节点, [左子树的前序遍历], [右子树的前序遍历]]
  

• 中序遍历序列：

    [[左子树的中序遍历], 根节点, [右子树的中序遍历]]
  

• 后序遍历序列：

    [[左子树的后序遍历], [右子树的后序遍历], 根节点]
  

因此，我们由后序遍历和中序遍历构造二叉树的步骤为：

1. 在后序遍历序列中得到根节点
2. 在中序遍历序列中找到根节点的位置，其左边为左子树中序遍历序列，右边为右子树中序遍历序列。
3. 在后序遍历序列中也找到左右子树对应的后序遍历序列（根据一棵树的中序遍历序列和后序遍历序列的长度相同）
4. 递归生成左右子树
5. 将根节点与左右子树连接

为了降低空间复杂度，我们不对原树的preorder和inorder切分生成新的数组序列，而是采用双指针记下子树的序列在preorder和inorder的索引范围

代码

class Solution {
    private static int[] inorder;
    private static int[] postorder;
    static HashMap<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.inorder = inorder;
        this.postorder = postorder;
        //用一个哈希表将中序遍历序列的每个元素和其下标对应起来，方便之后在inorder中查找根节点位置索引
        map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++)
            map.put(inorder[i], i);
        return helper(0, inorder.length, 0, postorder.length);
    }
    //由中序遍历序列和后序遍历序列构造二叉树
    //后序遍历序列由postorder中索引po_start和po_end间的元素构成
    //中序遍历序列由inorder中索引in_start和in_end间的元素构成
    private static TreeNode helper(int in_start, int in_end, int po_start, int po_end){
        if(po_start == po_end || in_start == in_end)
            return null;
        //后序遍历序列的最后一个元素为根节点
        int root_val = postorder[po_end - 1];
        TreeNode root = new TreeNode(root_val);
        //在中序遍历序列中找到根节点的位置索引
        int root_index = map.get(root_val);
        //左子树的后序遍历序列和中序遍历的长度
        int left_num = root_index - in_start;
        TreeNode L = helper(in_start, root_index, po_start, po_start + left_num);
        TreeNode R = helper(root_index + 1, in_end, po_start + left_num, po_end - 1);
        root.left = L;
        root.right = R;
        return root;
    }
}

• 时间复杂度：O(n), n为树中节点的个数
• 空间复杂度：O(n), 需要用O(n)存储哈希表，O(h)存储递归时的栈空间（h为树高度 h < n）,因此空间复杂度为O(n)