LeetCode 剑指 Offer 07. 重建二叉树

Categories:

题目描述
思路分析
1. 解法一：递归 + 哈希表（推荐）
相似题目

题目描述

✅ 剑指 Offer 07. 重建二叉树

思路分析

解法一：递归 + 哈希表（推荐）

核心思路：

前序遍历首元素为根节点。

在中序遍历中找到根节点位置，左侧为左子树，右侧为右子树。

递归构建左右子树，并用哈希表加速定位中序下标。

复杂度分析：

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

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

// 前序 + 中序递归建树
class Solution {
    private int preIndex = 0;
    private Map<Integer, Integer> inIndex;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inIndex = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inIndex.put(inorder[i], i);
        }
        return build(preorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int left, int right) {
        if (left > right) {
            return null;
        }
        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);
        int mid = inIndex.get(rootVal);
        root.left = build(preorder, left, mid - 1);
        root.right = build(preorder, mid + 1, right);
        return root;
    }
}

// 前序 + 中序递归建树
func buildTree(preorder []int, inorder []int) *TreeNode {
	index := make(map[int]int)
	for i, v := range inorder {
		index[v] = i
	}

	pre := 0
	var build func(int, int) *TreeNode
	build = func(left, right int) *TreeNode {
		if left > right {
			return nil
		}
		rootVal := preorder[pre]
		pre++
		root := &TreeNode{Val: rootVal}
		mid := index[rootVal]
		root.Left = build(left, mid-1)
		root.Right = build(mid+1, right)
		return root
	}

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

相似题目

题目	难度	考察点
105. 从前序与中序遍历序列构造二叉树	中等	递归
106. 从中序与后序遍历序列构造二叉树	中等	递归
889. 根据前序和后序遍历构造二叉树	中等	递归
114. 二叉树展开为链表	中等	递归
98. 验证二叉搜索树	中等	DFS
617. 合并二叉树	简单	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/67552711