LeetCode 105. 从前序与中序遍历序列构造二叉树

Categories:

Tags:

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

题目描述

✅ 105. 从前序与中序遍历序列构造二叉树

思路分析

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

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

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

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

参考代码

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

	// 前序遍历的第一个元素是根节点
	rootVal := preorder[0]
	root := &TreeNode{Val: rootVal}

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

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

	return root
}

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

	inMap := make(map[int]int)
	for i, val := range inorder {
		inMap[val] = i
	}

	var build func(preLeft, preRight, inLeft, inRight int) *TreeNode

	build = func(preLeft, preRight, inLeft, inRight int) *TreeNode {
		if preLeft > preRight || inLeft > inRight {
			return nil
		}

		// 根节点是前序的第一个元素
		rootVal := preorder[preLeft]
		root := &TreeNode{Val: rootVal}

		// 找到 root 在中序遍历中的位置
		inRootIndex := inMap[rootVal]

		// 左子树的节点个数
		leftSize := inRootIndex - inLeft

		root.Left = build(preLeft+1, preLeft+leftSize, inLeft, inRootIndex-1)
		root.Right = build(preLeft+leftSize+1, preRight, inRootIndex+1, inRight)

		return root
	}

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

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

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