统一给出二叉树三种遍历（前序 / 中序 / 后序）的迭代写法，每一种都分为三部分：

1. 代码
2. 核心思路
3. 可复用的套路总结

为便于对比，默认二叉树节点定义如下（LeetCode 风格）：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

---

一、前序遍历（Root → Left → Right）

1️⃣ 代码（迭代）

def preorderTraversal(root):
    if not root:
        return []
 
    res = []
    stack = [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

---

2️⃣ 思路

• 前序遍历：先访问当前节点

• 使用栈模拟递归调用栈

• 每次：

  1. 弹出栈顶节点
  2. 立刻记录其值
  3. 先压右子树，再压左子树（保证左子树先处理）

---

3️⃣ 套路总结

前序遍历 = 访问节点时立刻处理

• 栈初始化：stack = [root]
• 弹出即访问
• 压栈顺序：右 → 左

---

一、一句话先记住（最重要）

前序遍历 = 看见一个节点，立刻记录它，然后先左后右

记忆口诀：

“先记自己，再走左边，最后走右边”

---

二、先看最简单的代码（别急着理解）

def preorderTraversal(root):
    if not root:
        return []

    res = []
    stack = [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

你现在只需要注意 3 行：

node = stack.pop()
res.append(node.val)

👉 一弹出来，立刻记下来
这就是「前序」的本质。

---

三、为什么要用「栈」？（最白话解释）

想象你在走迷宫 / 爬树：

• 每到一个路口（节点）

• 你要记住：

  • 我是从哪来的？
  • 右边的路一会儿还要不要回来？

栈 = 备忘录

• 先写下“以后要回来的地方”
• 当前先走你最想走的路

---

四、一步一步模拟（非常关键）

示例二叉树

      1
     / \
    2   3

前序遍历答案应该是：[1, 2, 3]

---

Step 0：初始化

stack = [1]
res = []

---

Step 1：弹出 1

弹出：1
记录：1

res = [1]

然后你要决定：

• 左子树要先走
• 右子树以后再走

所以：先把右放进栈，再放左

stack = [3, 2]

（注意：2 在上面，下一次先弹 2）

---

Step 2：弹出 2

弹出：2
记录：2

res = [1, 2]

2 没有左右子树，什么也不放

stack = [3]

---

Step 3：弹出 3

弹出：3
记录：3

res = [1, 2, 3]

栈空，结束

---

五、最容易错的一点（99% 新手卡这里）

❌ 错误写法

stack.append(node.left)
stack.append(node.right)

为什么错？

• 栈是 后进先出
• 你如果先放左，再放右
• 右会先出来

✅ 正确顺序（一定要背）

先放右，再放左

👉 口诀：想先走谁，就让谁后进栈

---

六、把代码压缩成“傻瓜三步法”

永远不变的三步

1️⃣ 从栈里拿一个节点
2️⃣ 立刻记录它
3️⃣ 把它的孩子放回栈里（右先左后）

---

七、为什么这就等价于递归？

递归版本是：

visit(root)
preorder(root.left)
preorder(root.right)

迭代做的事情是：

• visit：res.append(node.val)
• left / right：用栈“记住还没走的路”

👉 栈就是“手写递归”

---

八、给小白的终极记忆卡片

前序遍历（迭代）=

• 用一个栈
• 弹出来就记录
• 右孩子先入栈
• 栈空就结束

---

九、如果你在考场 / 面试中突然忘了

只问自己一句话：

“前序是不是一看到节点就要处理它？”

如果答案是「是」
那你就知道：

node = stack.pop()
res.append(node.val)

一定写在一起。

---

二、中序遍历（Left → Root → Right）

1️⃣ 代码（迭代）

class solution:
    def ineOrder(root: TreeNode) -> list[int]:
        if not root:
            return []

        res = []
        stack = []
        cur=root

        while cur or stack:# 能「自动回溯」#用栈模拟递归
            if cur:
                stack.append(cur)
                cur=cur.left
            else:
                cur=stack.pop()#stack.pop() → 回到最近的祖先节点,继续执行中序逻辑
                res.append(cur.val)#这个是中
                cur=cur.right#右
                
        return res

---

2️⃣ 思路

• 中序遍历的关键：左子树访问完，才能访问根

• 不能像前序那样“弹出就访问”

• 用一个指针 cur 不断向左走，把路径压栈

• 左走到底后：

  1. 弹栈（此时才访问）
  2. 转向右子树

---

一、先给一句“人话版定义”（一定要先记这个）

中序遍历 = 左边走完了，才能记自己，然后再去右边

记忆口诀：

“左 → 记 → 右”
“不走到最左，绝不记”

这句话非常重要，后面所有代码都是为了实现它。

---

一、先把「后序递归」拆到“最原子”的层面

你的递归代码是：

def dfs(node):
    if not node:
        return
    dfs(node.left)
    dfs(node.right)
    res.append(node.val)

---

一、先给一句“结论版理解”

双栈法本质：

把「后序：左 → 右 → 中」
转换成「中 → 右 → 左」，
然后整体反过来。

这是唯一需要记住的核心。

---

二、先给标准双栈代码（你一定会见到的版本）

if not root:
            return []

        res = []
        stack = [root]
        
        while stack:
            node=stack.pop()
            res.append(node.val)
            
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)

        

        return res[::-1]

---