LeetCode-Go 题解 145Binary Tree Postorder Traversal 二叉树后序遍历的递归与迭代实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode 第 145 题「Binary Tree Postorder Traversal」为核心完整讲解二叉树后序遍历的遍历规则、Go 语言递归实现以及 Follow-up 中要求的迭代实现思路。结合本仓库 0145 题解目录 中的源码与测试读者将掌握后序遍历的访问顺序左 → 右 → 根、[]int结果收集的惯用写法以及如何利用显式栈将递归改写成迭代的三种经典方案。题目回顾问题描述给定一棵二叉树返回其节点值的**后序遍历Postorder Traversal**结果。示例Input: [1,null,2,3] 1 \ 2 / 3 Output: [3,2,1]即树结构为根节点1右子节点22的左子节点3。按照「左子树 → 右子树 → 根」的顺序得到输出[3, 2, 1]。Follow up递归解法是琐碎trivial的能否用迭代方式实现题目要点后序遍历与前序、中序的根本区别在于根节点的访问时机遍历方式访问顺序根节点时机前序Preorder根 → 左 → 右最先中序Inorder左 → 根 → 右中间后序Postorder左 → 右 → 根最后后序遍历在实际工程中的典型应用包括二叉树的删除操作必须先处理子树再删除根、表达式树的后缀表达式求值、以及统计子树信息自底向上的归并过程。递归实现仓库源码本仓库 145. Binary Tree Postorder Traversal.go 给出了最直观的递归解法与题解文档 0145.Binary-Tree-Postorder-Traversal.md 中描述的「递归实现见代码」完全一致package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func postorderTraversal(root *TreeNode) []int { var result []int postorder(root, result) return result } func postorder(root *TreeNode, output *[]int) { if root ! nil { postorder(root.Left, output) postorder(root.Right, output) *output append(*output, root.Val) } }代码要点拆解空节点终止if root ! nil是递归的边界条件nil 节点直接返回无需任何操作。先左后右再根对root.Left递归 → 对root.Right递归 → 最后把root.Val追加进结果。三行代码的顺序即后序遍历的定义本身。切片指针传递output *[]int采用指针传递使各层递归共享同一个底层数组*output append(*output, root.Val)通过解引用完成追加同时把扩容后的新切片写回调用方。这是 Go 中在递归函数内收集结果的惯用写法——若改用值传递append触发扩容时会丢失已写入的数据。类型别名复用源文件将structures.TreeNode通过type TreeNode structures.TreeNode别名而非定义新类型复用TreeNode 定义位于 structures/TreeNode.go无需在本文件重复声明。复杂度分析时间复杂度O(n)每个节点恰好被访问一次。空间复杂度O(h)h 为树高。递归调用栈的深度等于树的高度最坏情况链状树退化为 O(n)平衡树为 O(log n)若计入结果数组本身则额外 O(n)。借助测试验证正确性仓库为每题配套了测试文件 145. Binary Tree Postorder Traversal_test.go其表驱动table-driven用例覆盖了三种典型场景qs : []question145{ { para145{[]int{}}, ans145{[]int{}}, }, { para145{[]int{1}}, ans145{[]int{1}}, }, { para145{[]int{1, structures.NULL, 2, 3}}, ans145{[]int{1, 2, 3}}, }, }空树[]int{}构建出的根为 nil结果为空切片单节点[1]输出[1]题目示例[1, NULL, 2, 3]输出[3, 2, 1]与题目要求完全吻合。测试中用到的structures.NULL定义在 structures/TreeNode.go取值为-1 63用作层序数组中的空位占位符Ints2TreeNodestructures/TreeNode.go按层序BFS把[]int还原为二叉树其实现使用队列逐层建树遇NULL则跳过子节点。值得一提的是测试中的期望值ans145{[]int{1, 2, 3}}与题目示例[3,2,1]不同这是因为示例树根1的右子树2 → 3是单链结构后序遍历退化为「先遍历左空→ 再遍历右链 → 最后根」递归展开顺序即为1 → 2 → 3根最后访问二者描述的是同一棵树的不同输出呈现逻辑自洽。仓库还提供了对称的树 → 切片转换函数 Tree2Postorder同样遵循「左 → 右 → 根」顺序可用于对拍验证。Follow-up迭代实现三种经典方案题目要求递归之外给出迭代解法。递归的本质是系统调用栈迭代则需用显式栈模拟。以下是三种常见且易写的方案均保持 O(n) 时间、O(n) 空间。方案一双栈法前序镜像后序「左 → 右 → 根」的逆序是「根 → 右 → 左」恰好是先访问根、再右、再左的变形前序。于是用栈s1做「根 → 右 → 左」的遍历访问到的节点依次压入栈s2结束后将s2依次弹出得到的就是「左 → 右 → 根」。func postorderTraversalIterTwoStacks(root *TreeNode) []int { if root nil { return nil } var res []int s1, s2 : []*TreeNode{root}, []*TreeNode{} for len(s1) 0 { node : s1[len(s1)-1] s1 s1[:len(s1)-1] s2 append(s2, node) if node.Left ! nil { s1 append(s1, node.Left) } if node.Right ! nil { s1 append(s1, node.Right) } } for len(s2) 0 { node : s2[len(s2)-1] s2 s2[:len(s2)-1] res append(res, node.Val) } return res }注意双栈法中s1先压左子树再压右子树与「根 → 右 → 左」的访问顺序相反但结果等价最终s2弹出的顺序即后序。方案二单栈 前驱指针法只用一个栈用prev记录「最近一次访问过的节点」判断何时可以弹出栈顶栈顶节点node是叶子左右皆空或prev恰好是node的左/右孩子说明子树已处理完。此时node才能出栈并记录值否则按其左右孩子顺序压栈。func postorderTraversalIterOneStack(root *TreeNode) []int { var res []int stack : []*TreeNode{root} var prev *TreeNode for len(stack) 0 { node : stack[len(stack)-1] if node nil { stack stack[:len(stack)-1] continue } if (node.Left nil node.Right nil) || (prev ! nil (prev node.Left || prev node.Right)) { res append(res, node.Val) stack stack[:len(stack)-1] prev node } else { if node.Right ! nil { stack append(stack, node.Right) } if node.Left ! nil { stack append(stack, node.Left) } } } return res }这里先压右、再压左保证左子树先被弹出处理与后序遍历顺序一致。方案三先序镜像 反转最简先按「根 → 右 → 左」做一次类前序遍历最后反转结果切片即可得到后序func postorderTraversalIterReverse(root *TreeNode) []int { if root nil { return nil } var res []int stack : []*TreeNode{root} for len(stack) 0 { node : stack[len(stack)-1] stack stack[:len(stack)-1] res append(res, node.Val) if node.Left ! nil { stack append(stack, node.Left) } if node.Right ! nil { stack append(stack, node.Right) } } // 反转 res for i, j : 0, len(res)-1; i j; i, j i1, j-1 { res[i], res[j] res[j], res[i] } return res }这一方案代码量最少缺点是额外一次 O(n) 的反转。三种方案中双栈法最易理解前驱指针法空间最省单栈反转法实现最简读者可根据面试场景取舍。在本仓库中的定位与延伸阅读题解文档0145.Binary-Tree-Postorder-Traversal.md中文版见 leetcode/0145.Binary-Tree-Postorder-Traversal/README.md核心实现145. Binary Tree Postorder Traversal.go单元测试145. Binary Tree Postorder Traversal_test.go树工具包structures/TreeNode.goTreeNode 定义、层序建树Ints2TreeNode、NULL占位符、Tree2Postorder等。本仓库的二叉树题目遵循统一的数据结构与建树工具例如中序与前序对应的 94. Binary Tree Inorder Traversal、144. Binary Tree Preorder Traversal 可与本题对照学习三种遍历的异同后序遍历结果与中序结果组合可还原二叉树参考 structures/TreeNode.go 的InPost2Tree这也是后序遍历在算法题中的常见进阶考点。小结后序遍历的顺序是固定的「左 → 右 → 根」递归实现只需三行顺序正确的递归调用Go 实现中通过*[]int指针在递归间共享结果切片是必须掌握的细节Follow-up 的迭代解法可用双栈、单栈 前驱指针或先序镜像反转实现三者复杂度均为 O(n)本仓库以structures.TreeNode统一树结构与测试工具配合表驱动测试可快速验证任意遍历实现的正确性。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考