二叉树前序遍历

顺序

根 → 左 → 右

        1
       / \
      2   3
     / \
    4   5

前序：1 → 2 → 4 → 5 → 3

---

递归写法

def preorder(root):
    if not root:
        return
    print(root.val)          # 根
    preorder(root.left)      # 左
    preorder(root.right)     # 右

---

迭代写法（用栈模拟）

def preorder(root):
    if not root:
        return []
    stack, res = [root], []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:           # 先压右，后压左
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

关键：右子节点先入栈，左子节点后入栈——出栈时左先出，保证”根左右”顺序。

---

三种遍历对比

遍历	顺序	典型用途
前序	根 → 左 → 右	复制树、序列化
中序	左 → 根 → 右	BST 有序输出
后序	左 → 右 → 根	删除树、计算表达式

---

与快速排序的关系

快排的递归结构和前序遍历同构：

前序遍历            快速排序
─────────────       ─────────────────────
处理当前节点   ↔    partition（pivot 归位）
递归左子树     ↔    递归左半段
递归右子树     ↔    递归右半段

快排构造的隐式二叉树，每个节点就是一次 pivot 归位的位置。

→ 见快速排序的思路