中序遍历天然有序因bst左
递归遍历BST：中序遍历为什么天然有序
BST 的结构决定了中序遍历（左→根→右）必然输出升序序列。递归写法简洁，但要注意栈深度限制——树退化成链表时，sys.getrecursionlimit() 可能被突破。
实操建议：
- 用
def inorder(node):封装，空节点直接return，避免额外判断 - 若需返回列表而非打印，用
result = []作为参数传入，或用yield实现生成器（节省内存） - 不要在递归里反复调用
node.left或node.right多次——先存为局部变量，避免属性访问开销
非递归中序遍历：用栈模拟系统调用栈
本质是手动维护“待访问的父节点”——每次向左走到头，再弹出一个节点处理，然后跳到其右子树。关键在于理解栈里只存“还没处理完右子树的节点”。
常见错误现象：
- 忘记在处理完当前节点后转向
node.right，导致无限循环或漏遍历 - 把
node = node.right写在 while 循环外，只走一次右子树 - 初始时没把 root 入栈，或空树时未做判空，触发
AttributeError
标准写法骨架：
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
# 处理 node.val
node = node.right
前序/后序非递归实现：栈中元素顺序和弹出时机不同
前序（根→左→右）最简单：栈中压入右再压左，保证左先弹出；后序最难，需双栈或标记法。多数场景下，后序非递归不如递归直观，除非明确有栈深限制。
要点对比：
- 前序非递归：
stack = [root]开始，每次 pop 后按[right, left]顺序 push 子节点 - 后序双栈法：第一栈按
[left, right]压，第二栈接收弹出节点，最后反向输出——实际等于“根→右→左”的逆序 - 单栈后序：每个节点首次访问时标记
visited=False，第二次才真正处理——增加内存开销，且易错在标记逻辑
性能与兼容性：什么时候该放弃非递归
纯遍历场景下，递归比非递归快 10%–20%，因为函数调用开销已被 CPython 优化，而手动栈涉及更多 Python 对象操作。只有当树深度 > 1000 且无法调高 sys.setrecursionlimit() 时，才值得切非递归。
容易被忽略的点：
- LeetCode 等平台默认递归限制约 1000，但真实服务中可能更低（如某些嵌入式 Python 环境）
-
__iter__协议推荐用生成器递归实现，既保持可读性，又支持for x in bst:这种自然语法 - 如果 BST 节点带 parent 指针，后序可不用栈——从最左节点出发，靠 parent 和左右子节点状态回溯，但这种设计极少出现在实际项目中
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
