二叉树的前序遍历：根最先
根总是早于自己的子孙出现。迭代要先压右再压左，因为栈后进先出，后压的左孩子才会先出来。
前序 = 根 → 左子树 → 右子树。递归：先写入根，再递归左，再递归右。迭代用栈：弹出立刻访问，先压右孩子再压左孩子，左孩子后进先出，实际顺序仍是左子树先于右子树。时间 O(n)，空间 O(h)。
这是 LeetCode 144. Binary Tree Preorder Traversal。大白话：给你一棵二叉树的根节点，按「根、左子树、右子树」的顺序把节点值收进数组返回。前序的第一条规律：整棵树的根永远是序列的第一个元素。
本页先走一棵只有右脊的树：根 1，右孩子 2，2 的左孩子 3，层序写作 [1, null, 2, 3]。前序先写下 1，左子树空，进入右子树根 2，再进入 2 的左孩子 3，序列是 [1, 2, 3]。1 在一切之前，2 在 3 之前。
递归和定义同构，最容易写对。迭代不是另一种顺序，只是把系统调用栈改成显式栈。缺的是入栈顺序：栈是后进先出，想让左孩子先被访问，就必须后压左、先压右。说不清这一点，就会在「先压哪边」上猜硬币。
前序的契约：根最先
每个节点都要做三件事：处理自己、走完左子树、走完右子树。前序把处理放在最前，所以根总是早于自己的全部子孙。子树内部仍然遵循「根最先」，所以它是自然的递归结构：对节点 x，先写 x.Val，再对左孩子做前序，再对右孩子做前序。空节点直接返回。
主例 [1, null, 2, 3] 用手走一遍。访问 1，先写下 1。1 的左孩子空，进入右孩子 2，写下 2。进入 2 的左孩子 3，写下 3，3 的左右都空。序列是 [1, 2, 3]。根 1 在一切之前，根 2 在自己的子孙 3 之前。
换一棵左右都有孩子的树 [1, 2, 3]，前序是 [1, 2, 3]：先写 1，再整棵左子树 2，再整棵右子树 3。和上一棵树数字碰巧相同，形状不同——上一棵 3 是 2 的左孩子，这一棵 2 和 3 是 1 的左右孩子。前序只保证「根早于子孙」，不保证层序关系。空树返回空数组。
子结构每棵子树都先访问根，再处理左右——递归与定义同构。序列的第一个元素必是整棵树的根，这是从前序重建二叉树时取根的依据。
迭代版：栈先压右再压左
递归的本质是系统栈。当前节点写下自己之后，还要先走左再走右；系统把「右子树还没走」这件事记在调用栈里。迭代版用显式栈模拟同一份记忆：栈里先放根；每次弹出一个节点，立刻写入答案，然后先压右孩子、再压左孩子。
为什么先压右？栈是后进先出——后压的先出。后压左孩子，左孩子先被拿出来，于是实际顺序仍是左子树先于右子树，符合「根、左、右」。先压左再压右，弹出顺序会变成根、右、左，那是后序反转技巧用的变体，不是前序。
用 [1, 2, 3] 弹栈。栈先放 1。弹出 1，写入 1，先压右孩子 3，再压左孩子 2，栈里是 [3, 2]。弹出 2，写入 2，2 没有孩子。弹出 3，写入 3。写入顺序是 [1, 2, 3]。栈里同时存在的是「已经看见、但右子树还没轮到」的人，和递归时挂起的那些帧是同一批责任。
空节点不要压进去，或者压了弹出时跳过。每个节点入栈出栈各一次，时间 O(n)；栈最深是树高。前序迭代比中序更直：弹出立刻写，不必先一路向左推迟处理。
Go：递归与迭代
func preorderTraversal(root *TreeNode) []int {res := []int{}var dfs func(*TreeNode)dfs = func(n *TreeNode) {if n == nil { return }res = append(res, n.Val)dfs(n.Left)dfs(n.Right)}dfs(root)return res}// 迭代版func preorderIter(root *TreeNode) []int {res := []int{}stack := []*TreeNode{root}for len(stack) > 0 {n := stack[len(stack)-1]stack = stack[:len(stack)-1]if n == nil { continue }res = append(res, n.Val)stack = append(stack, n.Right, n.Left)}return res}
1递归：空节点返回；否则先把根写入答案，再递归左、再递归右。写入那一行在最前，就是前序。
2迭代栈先放根。弹出立刻访问，对应「根最先」。
3append(stack, n.Right, n.Left) 先压右再压左。后压的左孩子先出栈，实际仍是左子树优先。
4n == nil 则跳过，这样空根、空孩子都不必在入栈前单独判断。每个节点进出栈一次。
总结
前序根最先；递归直译定义，迭代先压右再压左，让左孩子后进先出。
- 序列的第一个元素必是根。子树内部同样根最先，所以递归与定义同构。
- 栈是后进先出：想让左先被访问，就必须后压左、先压右。左右压反，得到的是根、右、左。
- 迭代不是另一种遍历，只是把「右子树还没走」从系统栈搬到显式栈。