前序遍历（Pre-order Traversal）

一句话说明

前序遍历就是“先处理当前节点，再递归左右子树”，所以它特别适合把状态从上往下传。

顺序先记死

根 -> 左 -> 右

示例：

      1
     / \
    2   3
   / \
  4   5

前序结果：

[1, 2, 4, 5, 3]

为什么前序适合“自顶向下”

因为前序位置发生在刚进入节点时：

• 父节点信息还在
• 路径状态还没丢
• 左右子树还没开始处理

所以前序特别适合：

• 复制树
• 序列化树
• 路径记录
• 根到叶问题

Go 代码：递归前序

func PreorderTraversal(root *TreeNode) []int {
    result := []int{}
 
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        result = append(result, node.Val)
        dfs(node.Left)
        dfs(node.Right)
    }
 
    dfs(root)
    return result
}

Go 代码：迭代前序

func PreorderTraversalIterative(root *TreeNode) []int {
    if root == nil {
        return nil
    }
 
    result := []int{}
    stack := []*TreeNode{root}
 
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, node.Val)
 
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }
 
    return result
}

为什么迭代版要“先右后左”

因为栈是后进先出。
你想让左子树先处理，就要让它后入栈，所以顺序必须是：

1. 先压右
2. 再压左

常见题型

• 复制二叉树
• 二叉树序列化
• 收集根到叶路径
• 某些需要进入节点就更新状态的 DFS

易错点

前序遍历最常见的错误

• 处理当前节点的语句位置放错，就会变成中序或后序。
• 迭代写法里别把压栈顺序写反。

复杂度

实现方式	时间复杂度	空间复杂度
递归	O(n)	O(h)
迭代栈	O(n)	O(h)

相关主题

• 中序遍历
• 后序遍历
• 层序遍历
• 树算法

---

返回：树算法 | 算法学习导航