Go语言实现二叉树非递归遍历的三种方式

以下是Go语言实现二叉树非递归遍历的三种方式（前序、中序、后序），结合栈的特性实现，并附详细注释说明：

---

一、前序遍历（根-左-右）

核心逻辑：利用栈暂存右子节点，优先处理根节点和左子树
参考实现

func preorderTraversal(root *TreeNode) []int {
    var res []int
    if root == nil { return res }
    stack := []*TreeNode{root} // 初始化栈，根节点入栈

    for len(stack) > 0 {
        // 弹出栈顶元素（当前根节点）
        cur := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, cur.Val) // 先访问根节点

        // 先压右子节点（保证左子树先处理）
        if cur.Right != nil {
            stack = append(stack, cur.Right)
        }
        if cur.Left != nil {
            stack = append(stack, cur.Left)
        }
    }
    return res
}

---

二、中序遍历（左-根-右）

核心逻辑：通过栈回溯左子树路径，再处理右子树
参考实现

func inorderTraversal(root *TreeNode) []int {
    var res []int
    stack := []*TreeNode{}
    cur := root

    for len(stack) > 0 || cur != nil {
        // 将左子树全部入栈
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        // 弹出最深层左节点
        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, cur.Val) // 访问当前节点

        // 转向右子树
        cur = cur.Right
    }
    return res
}

---

三、后序遍历（左-右-根）

核心逻辑：使用双栈反转输出顺序，实现逆向存储
参考实现

func postorderTraversal(root *TreeNode) []int {
    var res []int
    if root == nil { return res }
    stack1 := []*TreeNode{root} // 主栈
    stack2 := []*TreeNode{}    // 辅助栈

    // 主栈按根-左-右顺序入栈，辅助栈反向存储
    for len(stack1) > 0 {
        cur := stack1[len(stack1)-1]
        stack1 = stack1[:len(stack1)-1]
        stack2 = append(stack2, cur) // 存入辅助栈

        // 左子节点先入主栈（后弹出）
        if cur.Left != nil {
            stack1 = append(stack1, cur.Left)
        }
        if cur.Right != nil {
            stack1 = append(stack1, cur.Right)
        }
    }

    // 辅助栈逆序输出（实际顺序左-右-根）
    for i := len(stack2)-1; i >= 0; i-- {
        res = append(res, stack2[i].Val)
    }
    return res
}

---

关键实现差异对比

---

代码示例数据结构

二叉树节点定义（需在代码前声明）：

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

---

扩展说明

1. 时间复杂度：三种遍历均为O(n)，每个节点入栈出栈各一次
2. 空间复杂度：前序和中序为O(h)（h为树高），后序为O(n)
3. 应用场景：
   • 前序：复制树结构、表达式前缀表示
   • 中序：二叉搜索树排序输出
   • 后序：内存释放、表达式后缀计算

若需要更高效的遍历（如Morris算法），可参考空间复杂度O(1)的非栈实现。