LeetCode 889. 根据前序和后序遍历构造二叉树

Categories:

题目描述
思路分析
1. 解法一：递归构造（推荐）
相似题目

题目描述

✅ 889. 根据前序和后序遍历构造二叉树

思路分析

解法一：递归构造（推荐）

核心思路：

前序遍历的第一个元素是根节点。

前序的下一个元素一定是左子树根，利用后序位置确定左子树大小。

递归构建左右子树，直到区间收敛。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数量。

空间复杂度：O(n)，递归栈与哈希表开销。

class Solution {
    private int preIndex = 0;
    private Map<Integer, Integer> postIndex = new HashMap<>();

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for (int i = 0; i < postorder.length; i++) {
            postIndex.put(postorder[i], i);
        }

        return build(preorder, postorder, 0, postorder.length - 1);
    }

    private TreeNode build(int[] preorder, int[] postorder, int left, int right) {
        TreeNode root = new TreeNode(preorder[preIndex++]);

        if (left == right) {
            return root;
        }

        int leftRootVal = preorder[preIndex];
        int leftRootIdx = postIndex.get(leftRootVal);

        // 左子树范围确定后，递归构建左右子树
        root.left = build(preorder, postorder, left, leftRootIdx);
        root.right = build(preorder, postorder, leftRootIdx + 1, right - 1);

        return root;
    }
}

func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
    pos := make(map[int]int)
    for i, v := range postorder {
        pos[v] = i
    }

    preIndex := 0

    var build func(int, int) *TreeNode
    build = func(left, right int) *TreeNode {
        root := &TreeNode{Val: preorder[preIndex]}
        preIndex++

        if left == right {
            return root
        }

        leftRootVal := preorder[preIndex]
        leftRootIdx := pos[leftRootVal]

        // 左子树范围确定后，递归构建左右子树
        root.Left = build(left, leftRootIdx)
        root.Right = build(leftRootIdx+1, right-1)

        return root
    }

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

相似题目

题目	难度	考察点
105. 从前序与中序遍历序列构造二叉树	中等	递归、哈希表
106. 从中序与后序遍历序列构造二叉树	中等	递归、哈希表
1008. 前序遍历构造二叉搜索树	中等	递归、BST
654. 最大二叉树	中等	递归、栈
889. 根据前序和后序遍历构造二叉树	中等	递归

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/58828253