【算法题解】48. 从中序与后序遍历序列构造二叉树

❝

这是一道 「中等难度」 的题
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

❞

题目

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

示例 1:

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

示例 2:

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

提示:

,
和都由不同的值组成
中每一个值都在中
保证是树的中序遍历
保证是树的后序遍历

题解

这道题和【算法题解】47. 从前序与中序遍历序列构造二叉树的解题思路是一样的。

使用后序遍历数组 postorder 确定根节点，然后使用中序遍历数组 inorder 划分左右子树。

以示例一为例：后序确定根节点 root = 3 。

利用中序遍历数组划分左右子树，并得到左右子树的中序遍历。

因为上一步知道了右子树的中序遍历，也就可以知道右子树的节点个数，假如是 m。

利用后序遍历数组，除去根节点后，从后往前依次取 m 个元素就是右子树的后序遍历，剩下的为左子树的后序遍历。

分别知道左右子树的后序和中序后，需要构建左右子树，构建左右子树就是重复上述步骤，也就是一个递归实现。

「边界条件」：只要中序和后序遍历为空了，就表示没有节点了，返回 null。

Java 代码实现

/**
 * 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) {
        for(int i = 0; i < inorder.length; i++){
            inorderIndexMap.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode build(int[] inorder, int il, int ir, int[] postorder, int pl, int pr) {
        // 边界条件
        if(il > ir){
            return null;
        }

        int rootValue = postorder[pr];
        TreeNode root = new TreeNode(rootValue);

        int rootInorderIndex = inorderIndexMap.get(rootValue);

        // 右子树的中序遍历位置为 rootInorderIndex + 1 到 ir, 

        // 右子树节点个数
        int m = ir - rootInorderIndex;

        // 右子树的后序遍历位置为 pr - m 到 pr - 1


        root.right = build(inorder, rootInorderIndex + 1, ir, postorder, pr - m, pr - 1);

        // 左子树的中序遍历位置为 il 到 rootInorderIndex - 1, 

        // 左子树的后序遍历位置为 pl 到 pr - m - 1

        root.left = build(inorder, il, rootInorderIndex - 1, postorder, pl, pr - m - 1);

        return root;

    }
}

Go 代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
    inorderIndexMap := make(map[int]int, 0)
    for i := 0; i < len(inorder); i++ {
        inorderIndexMap[inorder[i]] = i
    }

    var build func(il int, ir int, pl int, pr int) *TreeNode

    build = func(il int, ir int, pl int, pr int) *TreeNode {
        if il > ir {
            return nil
        }

        rootVal := postorder[pr]
        rootInorderIndex := inorderIndexMap[rootVal]

        root := &TreeNode{Val : rootVal}

        // 右子树 中序 rootInorderIndex + 1 到 ir
        // 左子树 中序 il 到 rootInorderIndex - 1

        // 右子树 节点数
        m := ir - rootInorderIndex

        // 右子树 后序 pr - m 到 pr - 1
        // 左子树 后序 pl 到 pr - m - 1

        root.Left = build(il, rootInorderIndex - 1, pl, pr - m - 1)
        root.Right = build(rootInorderIndex + 1, ir, pr - m, pr - 1)

        return root
    }

    return build(0, len(inorder) - 1, 0, len(postorder) - 1)
}