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

1. 题目

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

img

1
2
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

1
2
输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder 和 postorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder 中
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历

2. 思路

  • 已知二叉树的后序遍历为：左右根，中序遍历为：左根右，同时序列中无重复元素

  • 首先根据中序序列构建起哈希表，用于后续能够快速定位出根节点对应的下标位置

  • 已知中序遍历会自然地将二叉树划分为左子树 - 根节点 - 右子树，后序遍历的最后一个节点即为二叉树的根节点

  • 同时后序遍历中的最后一个节点必然为根节点，根据这个规律可以确定出中序遍历左右子树的范围，并进行二叉树的递归建立

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Map<Integer, Integer> inorderIndexMap = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        initIndexMap(inorder);

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

    private TreeNode helper(int[] inorder, int iStart, int iEnd, int[] postorder, int pStart, int pEnd) {
        if (iStart > iEnd || pStart > pEnd) {
            return null;
        }

        var rootVal = postorder[pEnd];
        var root = new TreeNode(rootVal);
        var pivot = inorderIndexMap.get(rootVal);
        var leftNodeSize = pivot - iStart;

        root.left = helper(inorder, iStart, pivot - 1, postorder, pStart, pStart + leftNodeSize - 1);
        root.right = helper(inorder, pivot + 1, iEnd, postorder, pStart + leftNodeSize, pEnd - 1);


        return root;
    }

    private void initIndexMap(int[] inorder) {
        for (var i = 0; i < inorder.length; ++i) {
            inorderIndexMap.put(inorder[i], i);
        }
    }
}

4. 复杂度

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

image-20231013222018333