【树】B022_从中序与后序遍历序列构造二叉树（递归）

一、题目描述

Given inorder and postorder traversal of a tree, construct the binary tree.

Note：You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

二、题解

方法一：模拟

思路

• 中序遍历是左根右。
• 后序遍历是左右根。

和 从中序与后序遍历序列构造二叉树 思路一样，我们需要确定根节点的位置 iRootID 。我们还是先从中序遍历找到根节点的位置。

算法

• 先存储中序遍历结果的各个结点的值与位置的映射。
• 后序遍历的末尾结点就是我们要找的根节点。
• 然后我们从中序遍历计算出根节点的左子树的大小 leftSize。
• 然后继续构造根节点的左右子树（边界需要注意）。

然后根据递归套路：

• 结束条件： 当以某一个结点为根构造不出左子树时，我们 return null。
  • 结束条件可以写成两种形式：
    • if (pS == pE) { return null; }
    • if (iS == iE) { return null; }

* 边界错误： 为什么应该写成 pS+leftSize ？因为此处的结点属于右子树的结点，还没有构造完毕，不能把该结点忽略。

root.right= dfs(iRootID+1, iE, pS+leftSize+1, pE-1); //不能写成+1

int[] postA;
Map<Integer, Integer> map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
    int N = inorder.length;
    postA = postorder;
    map = new HashMap<>();
    for (int i = 0; i < N; i++) 
        map.put(inorder[i], i);
        
    return dfs(0, N, 0, N);    
}
private TreeNode dfs(int iS, int iE, int pS, int pE) {
    if (pS == pE) {
        return null;
    }
    int rootVal = postA[pE-1];
    TreeNode root = new TreeNode(rootVal);
    
    int iRootID = map.get(rootVal);
    int leftSize = iRootID - iS;
    
    root.left = dfs(iS, iRootID, pS, pS + leftSize);
    root.right= dfs(iRootID+1, iE, pS + leftSize, pE-1);
    return root;
}

复杂度分析

• 时间复杂度：$O(n)$O(n)，
• 空间复杂度：$O(n)$O(n)，