94. 二叉树的中序遍历
一、算法逻辑（逐步通顺地讲解）
这段代码的目标是实现中序遍历，即按照顺序：
左子树 → 当前节点 → 右子树 遍历整个二叉树，并返回节点值的列表。
与常见的递归或传统栈方法不同，这里使用的是一种“统一写法”技巧，将“节点值访问”与“节点展开”分开处理，流程如下：
1️⃣ 初始化结构
使用一个栈保存待处理元素（可能是
TreeNode或int）；初始栈中放入整棵树的根节点；
结果数组
rst用来保存最终遍历的顺序。
2️⃣ 遍历栈（模拟递归展开）
不断从栈中弹出元素 i，分两种情况处理：
▶️ 情况一：i 是一个树节点（TreeNode）
说明它还没有“展开”处理；
根据中序遍历的顺序（左 → 根 → 右），将这三个部分按反顺序压入栈中：
stack.extend([i.right, i.val, i.left])为什么反着压？因为栈是“先进后出”，我们想要先处理左子树，所以左子树要最后压；
此时节点值（
i.val）是一个int，等到下一次遍历时会被识别为“已展开节点”，可以直接记录结果。
▶️ 情况二：i 是一个整数（int）
说明它是某个节点在之前压栈时留下的
.val；直接将它加入结果列表，相当于“真正访问”了该节点。
3️⃣ 遍历完成，返回结果
栈清空时，所有节点都已经以中序顺序访问，结果列表 rst 即为最终结果。
二、核心点总结
这段代码的关键在于：
将访问节点值与处理子节点的过程“解耦”，用类型判断区分是否“已展开”。
✅ 借助栈顺序控制访问流程；
✅ 用
isinstance(i, TreeNode)来判断当前栈元素是否是“待处理节点”；✅ 中序遍历通过压入
[右子树, 当前值, 左子树]的顺序来模拟递归。
这种技巧具有很高的统一性和可拓展性，适用于中序、前序、后序的迭代实现，只需要改变压栈顺序。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
stack, rst = [root], [] # 初始化栈和结果列表
while stack:
i = stack.pop() # 弹出栈顶元素
if isinstance(i, TreeNode):
# 按照中序遍历的顺序，将右子节点、节点值、左子节点依次压入栈
stack.extend([i.right, i.val, i.left])
elif isinstance(i, int):
# 如果节点值是 int 类型，输出其值
rst.append(i)
return rst三、时间复杂度分析
每个节点：
只会进入栈一次；
只会处理一次（包括子节点和节点值）；
因此总操作与节点数量成正比：
时间复杂度：O(n)，其中
n为节点数。
四、空间复杂度分析
最坏情况下：
所有节点都在一条边（退化为链表）时，栈深可达
n；加上结果数组存储节点值，也为 O(n)；
空间复杂度：O(n)
（注意：不考虑输出本身所占空间时，栈空间最坏 O(n)，平均 O(log n) 对于平衡树）
✅ 总结一句话
这段代码通过“栈统一展开 + 类型判断延迟访问值”的策略，实现了逻辑清晰、结构统一的中序遍历。核心思想在于利用类型和压栈顺序来控制遍历流程，不再显式管理递归或访问标记。