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

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

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

思路分析

我们可以使用递归的方法来构造二叉树。具体步骤如下：

后序遍历的最后一个元素是根节点。

在中序遍历中找到根节点的位置，根节点左边的部分是左子树，右边的部分是右子树。

递归地构造左子树和右子树。

参考代码

func buildTree(inorder []int, postorder []int) *TreeNode {
	if len(inorder) == 0 || len(postorder) == 0 {
		return nil
	}

	// 后序遍历的最后一个元素是根节点
	rootVal := postorder[len(postorder)-1]
	root := &TreeNode{Val: rootVal}

	// 在中序遍历中找到根节点的位置
	var rootIndex int
	for i, val := range inorder {
		if val == rootVal {
			rootIndex = i
			break
		}
	}

	// 递归构造左子树和右子树
	root.Left = buildTree(inorder[:rootIndex], postorder[:rootIndex])
	root.Right = buildTree(inorder[rootIndex+1:], postorder[rootIndex:len(postorder)-1])

	return root
}

func buildTree(inorder []int, postorder []int) *TreeNode {
	// 创建一个映射表，存储中序遍历中每个值的索引
	inorderIndexMap := make(map[int]int)
	for i, val := range inorder {
		inorderIndexMap[val] = i
	}

	var build func(inStart, inEnd, postStart, postEnd int) *TreeNode
	build = func(inStart, inEnd, postStart, postEnd int) *TreeNode {
		if inStart > inEnd || postStart > postEnd {
			return nil // 递归终止条件
		}
		rootVal := postorder[postEnd]   // 根节点的值
		root := &TreeNode{Val: rootVal} // 创建根节点

		// 在中序遍历中找到根节点的位置
		rootIndex := inorderIndexMap[rootVal]
		leftSize := rootIndex - inStart // 左子树的大小

		// 递归构建左子树和右子树
		root.Left = build(inStart, rootIndex-1, postStart, postStart+leftSize-1)
		root.Right = build(rootIndex+1, inEnd, postStart+leftSize, postEnd-1)

		return root
	}

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

时间复杂度：O (n)，其中 n 是节点的数量。我们需要遍历每个节点一次。

空间复杂度：O (n)，用于存储中序遍历的索引映射表和递归调用栈的空间。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/66276999