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

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

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

Go 语言里结构体是值类型，这一点和许多语言不同。如果你把左右子节点声明为非指针，比如写成 Left TreeNode，那么递归遍历时就会丢失连接——这几乎是初学二叉树的第一个大坑。正确做法很简单：

• 标准写法：type TreeNode struct { Val int; Left *TreeNode; Right *TreeNode }
• 如果用切片模拟树（比如力扣某些题用数组表示完全二叉树），注意下标映射：左子节点是 2*i + 1，右子是 2*i + 2。不过这属于数组表示法，和指针树是两码事。
• 空节点一律用 nil，千万别用零值结构体，否则 if node == nil 判断会失效，后面所有逻辑都会崩。

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

三种遍历的本质区别，说白了就是“访问根节点”这一步放在哪。递归代码几乎一模一样，但很多人容易在后序上翻车——把 append 放在最后，却忘了递归调用必须先完成才能执行它。

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

• 前序：append 在最前，然后左、右递归。
• 中序：左递归 → append → 右递归，如上。
• 后序：左递归 → 右递归 → append，注意左右递归必须已经返回，才能把当前节点值加进去。
• 切片拼接（append(...)）有一定开销，如果树很大且频繁调用，建议传入 []int 指针复用底层数组，能省不少资源。

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

Go 没有尾递归优化，树深度一旦超过几百层，递归就很容易栈溢出。生产环境更推荐迭代写法。核心思路是用 []*TreeNode 手动维护一个调用栈，关键难点在于“什么时候把节点加入结果”以及“如何判断子树是否已经访问过”。

• 前序迭代：先压右子节点，再压左子节点，每次 pop 后立即把值加入结果——因为根优先。
• 中序迭代：一路向左压栈，直到遇到 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 < levelSize; i++ {            node := queue[0]            queue = queue[1:] // 出队            level = append(level, node.Val)            if node.Left != nil {                queue = append(queue, node.Left) // 入队            }            if node.Right != nil {                queue = append(queue, node.Right)            }        }        res = append(res, level)    }    return res}

• 每次循环开始前记下当前队列长度，确保只处理本层节点，不会混入下一层。
• 不要在循环内动态修改 queue 长度后再用 range，那样会漏掉节点或触发 panic。
• 如果只需要每层的第一个或最后一个节点，可以在内层循环的开头或结尾取 queue[0] 或 queue[levelSize-1]，不必收集全部。

实际写代码时，递归够用就别硬套迭代；但一旦树深度超千级，或者要求 O(1) 栈空间，就得认真处理标记位和双栈逻辑。后序迭代的标记方案最容易漏掉“已访问过子树”的状态判断，多写几个测试用例就能发现。