LeetCode-Go 第 106 题实战用中序 后序遍历递归重建二叉树的两种 Go 实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇以 LeetCode-Go 仓库中的第 106 题文档为核心完整讲解“根据一棵树的中序遍历与后序遍历构造二叉树”这一经典递归重建问题的建模思路、边界约定与代码实现文中给出仓库中收录的两种 Go 解法切片下标递推 与 哈希表定位并结合仓库测试用例与structures包中的配套工具说明如何本地运行与验证读完你可以掌握“后序定根、中序定界”的通用递归框架以及两种实现在时间复杂度、内存占用上的取舍。题目与约束条件LeetCode 第 106 题Construct Binary Tree from Inorder and Postorder Traversal的题目描述如下Given inorder and postorder traversal of a tree, construct the binary tree.Note: You may assume that duplicates do not exist in the tree.即根据一棵二叉树的中序遍历inorder与后序遍历postorder序列重建出这棵二叉树。唯一的关键约束是树中不存在重复元素——这保证了在中序序列中查找根值时结果唯一是整题递归框架成立的前提。题目给出的官方示例inorder [9, 3, 15, 20, 7] postorder [9, 15, 7, 20, 3]应重建出如下二叉树3 / \ 9 20 / \ 15 7对应的英文题解文档位于 0106.Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal.md同目录题解的中文版在 leetcode/0106.Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal/README.md。解题思路后序定根中序定界原文档给出的解题思路Solution Idea可以概括为两点给定两个数组根据 inorder 和 postorder 数组构造一棵树利用递归思想从 postorder 可以得到根节点从 inorder 中得到左子树和右子树当只剩一个节点时即为根节点。不断递归直到所有树都生成完成。展开来说其数学依据是两种遍历的结构性差异后序遍历的最后一个元素永远是当前子树的根。设postorder [左子树序列, 右子树序列, 根]取postorder[len-1]即可拿到根的节点值中序遍历以根为分界点。inorder [左子树序列, 根, 右子树序列]找到根在中序中的下标pos后inorder[:pos]就是左子树的中序inorder[pos1:]就是右子树的中序左子树元素个数pos同时决定了后序中左右子树的切分位置postorder[:pos]是左子树的后序postorder[pos:]去掉已用掉的根是右子树的后序。于是每一步递归都遵循同一模式“取后序尾元素建根节点 → 在中序中定位根 → 按左右子树长度切分后序 → 递归左右”。递归出口是当前子树范围为空时返回nil叶子节点对应左、右两次空范围递归自然终止。仓库中节点的统一定义在 TreeNode.go 中// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode }题解代码通过类型别名type TreeNode structures.TreeNode直接复用该定义与仓库内其他题目保持结构一致。解法一直接传入切分后的子切片仓库收录的第一种解法见 106. Construct Binary Tree from Inorder and Postorder Traversal.go注释明确指出其设计动机直接传入需要的 slice 范围作为输入可以避免申请对应 inorder 索引的内存内存使用LeetCode 测试用例从 4.7MB 降到 4.3MB。// 解法一, 直接传入需要的 slice 范围作为输入, 可以避免申请对应 inorder 索引的内存, // 内存使用(leetcode test case) 4.7MB - 4.3MB. func buildTree(inorder []int, postorder []int) *TreeNode { postorderLen : len(postorder) if len(inorder) 0 { return nil } root : TreeNode{Val: postorder[postorderLen-1]} postorder postorder[:postorderLen-1] for pos, node : range inorder { if node root.Val { root.Left buildTree(inorder[:pos], postorder[:len(inorder[:pos])]) root.Right buildTree(inorder[pos1:], postorder[len(inorder[:pos]):]) } } return root }逐步拆解递归出口len(inorder) 0时返回nil即当前子树为空建根root : TreeNode{Val: postorder[postorderLen-1]}取后序最后一个元素随后postorder postorder[:postorderLen-1]把根从“可用后序”中扣除定位根遍历inorder找到与根值相等的位置pos。由于题目保证无重复元素循环内命中一次即完成切分Go 的切片共享底层数组inorder[:pos]、inorder[pos1:]并不复制元素只是新建了 slice 头这正是该解法省内存的原因递归切分左子树规模为pos故左子树后序取postorder[:pos]右子树后序从postorder[pos:]开始。两段递归分别挂载到root.Left与root.Right。该实现在时间上是 O(n²)每层都对子中序做一次线性扫描找根空间上为 O(n) 递归栈 O(n) 个共享底层数组的 slice 头但省去了额外的哈希表。解法二哈希表定位根 区间参数递归第二种解法同文件 L36-L55引入map把“找根下标”降到 O(1)递归参数只传区间边界而不是切分出的子切片// 解法二 func buildTree1(inorder []int, postorder []int) *TreeNode { inPos : make(map[int]int) for i : 0; i len(inorder); i { inPos[inorder[i]] i } return buildInPos2TreeDFS(postorder, 0, len(postorder)-1, 0, inPos) } func buildInPos2TreeDFS(post []int, postStart int, postEnd int, inStart int, inPos map[int]int) *TreeNode { if postStart postEnd { return nil } root : TreeNode{Val: post[postEnd]} rootIdx : inPos[post[postEnd]] leftLen : rootIdx - inStart root.Left buildInPos2TreeDFS(post, postStart, postStartleftLen-1, inStart, inPos) root.Right buildInPos2TreeDFS(post, postStartleftLen, postEnd-1, rootIdx1, inPos) return root }参数含义是“同一个原始postorder与inorder数组上的当前子树区间”参数含义postStart, postEnd当前子树在postorder中的后序区间闭区间根为post[postEnd]inStart当前子树在inorder中的起始下标inPos中的下标均相对全局 inorderinPos节点值 → 中序下标 的哈希表O(1) 定位根关键推导rootIdx : inPos[post[postEnd]]得到根在中序中的位置leftLen : rootIdx - inStart即左子树元素个数。据此切分后序区间左子树后序区间为[postStart, postStartleftLen-1]中序起点仍为inStart右子树后序区间为[postStartleftLen, postEnd-1]注意去掉根postEnd-1中序起点为rootIdx1。时间复杂度 O(n)建表 O(n) 每个节点一次查表空间 O(n)哈希表 递归栈。相比解法一它用 O(n) 额外内存换掉了每层的线性扫描是区间参数式递归的标准写法也便于移植到“前序 中序”第 105 题等同构问题。值得一提仓库的structures包里另有一份同思想的工具实现 InPost2Tree用indexOf线性查找根在中序中的下标后做同样的左右切分可作为上述两种解法之外的第三个对照样本// InPost2Tree 把 inorder 和 postorder 切片转换成 二叉树 func InPost2Tree(in, post []int) *TreeNode { ... res : TreeNode{Val: post[len(post)-1]} ... idx : indexOf(res.Val, in) res.Left InPost2Tree(in[:idx], post[:idx]) res.Right InPost2Tree(in[idx1:], post[idx:len(post)-1]) return res }测试用例与本地验证方式题目对应的测试文件是 106. Construct Binary Tree from Inorder and Postorder Traversal_test.go它验证了官方示例的完整输入输出qs : []question106{ { para106{[]int{9, 3, 15, 20, 7}, []int{9, 15, 7, 20, 3}}, ans106{[]int{3, 9, 20, structures.NULL, structures.NULL, 15, 7}}, }, } ... for _, q : range qs { _, p : q.ans106, q.para106 fmt.Printf(【input】:%v , p) fmt.Printf(【output】:%v \n, structures.Tree2ints(buildTree(p.inorder, p.postorder))) buildTree1(p.inorder, p.postorder) }测试的期望值[3, 9, 20, NULL, NULL, 15, 7]是重建结果树按层序还原的整数序列其中NULL是 TreeNode.go 中定义的哨兵常量var NULL -1 63用来在层序表示里占位表示空子节点。序列与题目树逐层对应第 1 层3第 2 层9, 20第 3 层9无子节点两个NULL占位、20的左右子为15, 7。序列化本身由 Tree2ints 完成用队列做层序遍历遇到nil节点追加NULL最后裁掉末尾连续的NULL。仓库同时提供 Tree2Preorder、Tree2Inorder、Tree2Postorder 三个反向工具——这正好构成本题的自洽校验闭环把重建出的树再做一遍中序、后序遍历应当分别得到原始的[9,3,15,20,7]与[9,15,7,20,3]。本地运行方式仓库根目录Go 1.19模块与本地replace依赖配置见 go.mod# 只跑第 106 题 go test -v -run Test_Problem106 ./leetcode/0106.Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal/ # 跑全量题解并生成覆盖率文件与仓库 gotest.sh 一致 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...全量覆盖率的官方生成脚本见 gotest.sh其产出即仓库根目录的 coverage.txt。小结本题的核心框架是“后序尾元素定根中序定位定界”pos根在中序中的下标同时承担“切中序”和“切后序”两个作用这是所有“遍历序列重建树”问题的通用骨架解法一buildTree用切片传参避免建表实测内存 4.7MB → 4.3MB代价是每层 O(n) 扫描整体 O(n²)解法二buildTree1用哈希表 区间参数实现 O(n) 重建是更通用的工程写法测试侧通过层序哨兵序列Tree2ints做结构断言再配合structures包的Tree2Inorder/Tree2Postorder可完成“序列 → 树 → 序列”的往返验证该框架可直接迁移到第 105 题前序 中序只需把“根在后序尾”换成“根在前序头”切分方向相应调整即可。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 第 106 题实战：用中序 + 后序遍历递归重建二叉树的两种 Go 实现
LeetCode-Go 第 106 题实战用中序 后序遍历递归重建二叉树的两种 Go 实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇以 LeetCode-Go 仓库中的第 106 题文档为核心完整讲解“根据一棵树的中序遍历与后序遍历构造二叉树”这一经典递归重建问题的建模思路、边界约定与代码实现文中给出仓库中收录的两种 Go 解法切片下标递推 与 哈希表定位并结合仓库测试用例与structures包中的配套工具说明如何本地运行与验证读完你可以掌握“后序定根、中序定界”的通用递归框架以及两种实现在时间复杂度、内存占用上的取舍。题目与约束条件LeetCode 第 106 题Construct Binary Tree from Inorder and Postorder Traversal的题目描述如下Given inorder and postorder traversal of a tree, construct the binary tree.Note: You may assume that duplicates do not exist in the tree.即根据一棵二叉树的中序遍历inorder与后序遍历postorder序列重建出这棵二叉树。唯一的关键约束是树中不存在重复元素——这保证了在中序序列中查找根值时结果唯一是整题递归框架成立的前提。题目给出的官方示例inorder [9, 3, 15, 20, 7] postorder [9, 15, 7, 20, 3]应重建出如下二叉树3 / \ 9 20 / \ 15 7对应的英文题解文档位于 0106.Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal.md同目录题解的中文版在 leetcode/0106.Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal/README.md。解题思路后序定根中序定界原文档给出的解题思路Solution Idea可以概括为两点给定两个数组根据 inorder 和 postorder 数组构造一棵树利用递归思想从 postorder 可以得到根节点从 inorder 中得到左子树和右子树当只剩一个节点时即为根节点。不断递归直到所有树都生成完成。展开来说其数学依据是两种遍历的结构性差异后序遍历的最后一个元素永远是当前子树的根。设postorder [左子树序列, 右子树序列, 根]取postorder[len-1]即可拿到根的节点值中序遍历以根为分界点。inorder [左子树序列, 根, 右子树序列]找到根在中序中的下标pos后inorder[:pos]就是左子树的中序inorder[pos1:]就是右子树的中序左子树元素个数pos同时决定了后序中左右子树的切分位置postorder[:pos]是左子树的后序postorder[pos:]去掉已用掉的根是右子树的后序。于是每一步递归都遵循同一模式“取后序尾元素建根节点 → 在中序中定位根 → 按左右子树长度切分后序 → 递归左右”。递归出口是当前子树范围为空时返回nil叶子节点对应左、右两次空范围递归自然终止。仓库中节点的统一定义在 TreeNode.go 中// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode }题解代码通过类型别名type TreeNode structures.TreeNode直接复用该定义与仓库内其他题目保持结构一致。解法一直接传入切分后的子切片仓库收录的第一种解法见 106. Construct Binary Tree from Inorder and Postorder Traversal.go注释明确指出其设计动机直接传入需要的 slice 范围作为输入可以避免申请对应 inorder 索引的内存内存使用LeetCode 测试用例从 4.7MB 降到 4.3MB。// 解法一, 直接传入需要的 slice 范围作为输入, 可以避免申请对应 inorder 索引的内存, // 内存使用(leetcode test case) 4.7MB - 4.3MB. func buildTree(inorder []int, postorder []int) *TreeNode { postorderLen : len(postorder) if len(inorder) 0 { return nil } root : TreeNode{Val: postorder[postorderLen-1]} postorder postorder[:postorderLen-1] for pos, node : range inorder { if node root.Val { root.Left buildTree(inorder[:pos], postorder[:len(inorder[:pos])]) root.Right buildTree(inorder[pos1:], postorder[len(inorder[:pos]):]) } } return root }逐步拆解递归出口len(inorder) 0时返回nil即当前子树为空建根root : TreeNode{Val: postorder[postorderLen-1]}取后序最后一个元素随后postorder postorder[:postorderLen-1]把根从“可用后序”中扣除定位根遍历inorder找到与根值相等的位置pos。由于题目保证无重复元素循环内命中一次即完成切分Go 的切片共享底层数组inorder[:pos]、inorder[pos1:]并不复制元素只是新建了 slice 头这正是该解法省内存的原因递归切分左子树规模为pos故左子树后序取postorder[:pos]右子树后序从postorder[pos:]开始。两段递归分别挂载到root.Left与root.Right。该实现在时间上是 O(n²)每层都对子中序做一次线性扫描找根空间上为 O(n) 递归栈 O(n) 个共享底层数组的 slice 头但省去了额外的哈希表。解法二哈希表定位根 区间参数递归第二种解法同文件 L36-L55引入map把“找根下标”降到 O(1)递归参数只传区间边界而不是切分出的子切片// 解法二 func buildTree1(inorder []int, postorder []int) *TreeNode { inPos : make(map[int]int) for i : 0; i len(inorder); i { inPos[inorder[i]] i } return buildInPos2TreeDFS(postorder, 0, len(postorder)-1, 0, inPos) } func buildInPos2TreeDFS(post []int, postStart int, postEnd int, inStart int, inPos map[int]int) *TreeNode { if postStart postEnd { return nil } root : TreeNode{Val: post[postEnd]} rootIdx : inPos[post[postEnd]] leftLen : rootIdx - inStart root.Left buildInPos2TreeDFS(post, postStart, postStartleftLen-1, inStart, inPos) root.Right buildInPos2TreeDFS(post, postStartleftLen, postEnd-1, rootIdx1, inPos) return root }参数含义是“同一个原始postorder与inorder数组上的当前子树区间”参数含义postStart, postEnd当前子树在postorder中的后序区间闭区间根为post[postEnd]inStart当前子树在inorder中的起始下标inPos中的下标均相对全局 inorderinPos节点值 → 中序下标 的哈希表O(1) 定位根关键推导rootIdx : inPos[post[postEnd]]得到根在中序中的位置leftLen : rootIdx - inStart即左子树元素个数。据此切分后序区间左子树后序区间为[postStart, postStartleftLen-1]中序起点仍为inStart右子树后序区间为[postStartleftLen, postEnd-1]注意去掉根postEnd-1中序起点为rootIdx1。时间复杂度 O(n)建表 O(n) 每个节点一次查表空间 O(n)哈希表 递归栈。相比解法一它用 O(n) 额外内存换掉了每层的线性扫描是区间参数式递归的标准写法也便于移植到“前序 中序”第 105 题等同构问题。值得一提仓库的structures包里另有一份同思想的工具实现 InPost2Tree用indexOf线性查找根在中序中的下标后做同样的左右切分可作为上述两种解法之外的第三个对照样本// InPost2Tree 把 inorder 和 postorder 切片转换成 二叉树 func InPost2Tree(in, post []int) *TreeNode { ... res : TreeNode{Val: post[len(post)-1]} ... idx : indexOf(res.Val, in) res.Left InPost2Tree(in[:idx], post[:idx]) res.Right InPost2Tree(in[idx1:], post[idx:len(post)-1]) return res }测试用例与本地验证方式题目对应的测试文件是 106. Construct Binary Tree from Inorder and Postorder Traversal_test.go它验证了官方示例的完整输入输出qs : []question106{ { para106{[]int{9, 3, 15, 20, 7}, []int{9, 15, 7, 20, 3}}, ans106{[]int{3, 9, 20, structures.NULL, structures.NULL, 15, 7}}, }, } ... for _, q : range qs { _, p : q.ans106, q.para106 fmt.Printf(【input】:%v , p) fmt.Printf(【output】:%v \n, structures.Tree2ints(buildTree(p.inorder, p.postorder))) buildTree1(p.inorder, p.postorder) }测试的期望值[3, 9, 20, NULL, NULL, 15, 7]是重建结果树按层序还原的整数序列其中NULL是 TreeNode.go 中定义的哨兵常量var NULL -1 63用来在层序表示里占位表示空子节点。序列与题目树逐层对应第 1 层3第 2 层9, 20第 3 层9无子节点两个NULL占位、20的左右子为15, 7。序列化本身由 Tree2ints 完成用队列做层序遍历遇到nil节点追加NULL最后裁掉末尾连续的NULL。仓库同时提供 Tree2Preorder、Tree2Inorder、Tree2Postorder 三个反向工具——这正好构成本题的自洽校验闭环把重建出的树再做一遍中序、后序遍历应当分别得到原始的[9,3,15,20,7]与[9,15,7,20,3]。本地运行方式仓库根目录Go 1.19模块与本地replace依赖配置见 go.mod# 只跑第 106 题 go test -v -run Test_Problem106 ./leetcode/0106.Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal/ # 跑全量题解并生成覆盖率文件与仓库 gotest.sh 一致 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...全量覆盖率的官方生成脚本见 gotest.sh其产出即仓库根目录的 coverage.txt。小结本题的核心框架是“后序尾元素定根中序定位定界”pos根在中序中的下标同时承担“切中序”和“切后序”两个作用这是所有“遍历序列重建树”问题的通用骨架解法一buildTree用切片传参避免建表实测内存 4.7MB → 4.3MB代价是每层 O(n) 扫描整体 O(n²)解法二buildTree1用哈希表 区间参数实现 O(n) 重建是更通用的工程写法测试侧通过层序哨兵序列Tree2ints做结构断言再配合structures包的Tree2Inorder/Tree2Postorder可完成“序列 → 树 → 序列”的往返验证该框架可直接迁移到第 105 题前序 中序只需把“根在后序尾”换成“根在前序头”切分方向相应调整即可。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考