golang如何实现二叉树遍历_golang二叉树遍历实现攻略-Golang-PHP中文网

二叉树节点必须用指针字段定义，如Left *TreeNode；三种递归遍历仅访问根节点顺序不同；迭代遍历需手动维护栈或队列，层序用切片模拟FIFO队列。

golang如何实现二叉树遍历_golang二叉树遍历实现攻略

二叉树节点定义必须包含指针字段

Go 里没有引用类型，所有结构体默认值拷贝，所以 TreeNode 的左右子节点必须声明为指针类型，否则递归遍历时会丢失连接。常见错误是写成 Left TreeNode，导致插入后子树无法被访问。

正确写法：type TreeNode struct { Val int; Left *TreeNode; Right *TreeNode }
如果用切片模拟树（如力扣部分题），注意索引计算：左子节点下标是 2*i + 1，右子是 2*i + 2，但这是数组表示法，和指针树无关
初始化空节点一律用 nil，别用零值结构体，否则 if node == nil 判断失效

递归实现前/中/后序遍历只需改语句顺序

三种遍历本质区别仅在于“访问根节点”这一步的位置，递归代码几乎一样。容易错的是后序把 append 放在最后却忘了递归调用必须先完成。

func inorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    var res []int
    res = append(res, inorderTraversal(root.Left)...)
    res = append(res, root.Val) // ← 中序：根在中间
    res = append(res, inorderTraversal(root.Right)...)
    return res
}

前序：访问 → 左 → 右（append 在最前）
中序：左 → 访问 → 右（如上）
后序：左 → 右 → 访问（append 在最后，且左右递归必须已返回）
注意切片拼接的开销，高频调用建议传入 []int 参数复用底层数组

迭代遍历必须用栈模拟系统调用栈

Go 没有尾递归优化，深度过大会栈溢出，生产环境建议迭代。核心是用 []*TreeNode 手动维护调用栈，关键点在于“什么时候把节点加入结果”以及“是否已访问过其子树”。

Golang Uber Dig

使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器，提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象，支持命名依赖等

下载

前序迭代：先压右再压左，每次 pop 后立即 append 值 —— 因为根优先
中序迭代：一路向左压栈，遇到 nil 就 pop 并记录值，再转向右子树
后序最难：标准做法是压栈时附带标记位，或用两个栈，或反向记录（根→右→左）再反转结果
别直接用 for range 遍历栈切片，要手动控制 len(stack) > 0 和 stack = stack[:len(stack)-1]

层序遍历依赖队列，但 Go 没内置，用切片模拟即可

层序本质是 BFS，需要 FIFO。用 []*TreeNode 模拟队列足够轻量，避免引入额外依赖。常见坑是误用栈逻辑（LIFO）导致变成 DFS。

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    var res [][]int
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        levelSize := len(queue)
        var level []int
        for i := 0; i