颜色标记法 / 模拟递归法
一、算法逻辑（逐步通顺地讲解）
这段代码的目标依然是实现 中序遍历（左 → 根 → 右），但它通过引入“颜色标记”的方式显式管理节点的访问状态。
🌱 初始化
定义两个常量
WHITE = 0（未访问），GRAY = 1（已访问/待处理）；初始化栈，根节点以
WHITE状态压入；准备结果列表
res。
🔁 栈模拟递归处理
每次从栈中弹出一个 (color, node) 元组：
✅ 如果 node 是空，跳过：
表示该子树为空，不需要处理。
✅ 如果 node 是白色（WHITE），说明它还没有被访问过：
按中序顺序压入相关节点，但要反着压栈（因为栈是“先进后出”）：
先右子树 → 再当前节点（标记为灰色）→ 再左子树
这样下一次从栈顶出来的就是左子树，模拟的是：
左 → 根（GRAY）→ 右
✅ 如果 node 是灰色（GRAY），说明它是“中间处理点”：
此时该节点的左子树已经处理过，右子树还没开始——正是访问当前节点值的正确时机，加入结果数组。
🏁 返回结果
所有节点处理完毕后，res 就是按中序顺序排列的节点值列表。
二、核心点总结
这段代码的核心在于：
通过颜色状态模拟递归流程，显式管理“节点处理的阶段”，从而完成中序遍历。
相比传统的栈模拟或统一写法，它具有以下优势：
✅ 清晰区分每个节点的处理阶段（未访问 / 待访问）；
✅ 适用于中序 / 前序 / 后序统一写法，仅需调整压栈顺序；
✅ 可用于复杂场景（如前序+后序同时记录、构建表达式树等）。
# 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]:
WHITE, GRAY = 0, 1 # 定义颜色常量
res = [] # 结果列表
stack = [(WHITE, root)] # 初始化栈，根节点以 WHITE 状态压入
while stack:
color, node = stack.pop() # 弹出栈顶元素
if node is None: continue # 如果节点为空，跳过
if color == WHITE:
# 按照中序遍历的顺序，将右子节点、当前节点、左子节点依次压入栈
stack.append((WHITE, node.right))
stack.append((GRAY, node))
stack.append((WHITE, node.left))
else:
# 如果节点是 GRAY 状态，输出其值
res.append(node.val)
return res三、时间复杂度分析
每个节点入栈两次（白色一次 + 灰色一次），每次处理耗时 O(1)；
总体处理与节点数量线性相关；
时间复杂度：O(n)，其中
n是树的节点数。
四、空间复杂度分析
最坏情况下所有节点都需要压入栈（树退化为链）；
所以栈的空间最坏为 O(n)，平均为 O(log n)（平衡树）；
结果数组也需要 O(n) 空间；
空间复杂度：O(n)（包含结果数组）