二叉树遍历是理解树结构的基础。面试官通过此题考察你对递归、基于栈的迭代以及在层次化数据上推理操作顺序的能力。
定义每种遍历顺序：中序（左-根-右）、前序（根-左-右）、后序（左-右-根）。
先实现递归版本——最简洁直观。
用显式栈展示迭代版本，体现更深的理解。
讨论使用场景：中序用于 BST 排序输出，前序用于序列化，后序用于删除或表达式求值。
中序遍历依次访问左子树、根节点、右子树——对 BST 可以得到有序输出。前序先访问根，再左再右——适合序列化或复制树。后序先左右再根——适合删除树或求解后缀表达式。递归实现只需三行代码，改变递归调用和访问的顺序即可。迭代中序用栈不断压入左子节点，弹出访问后转向右子节点。迭代前序压入根节点，弹出访问，先压右再压左。后序可用双栈法或反转修改版前序。三种遍历时间都是 O(n)，空间 O(h)，h 为树高。我总会提到迭代版本，因为它展示了将递归转化为显式状态管理的能力，对于非常深的树很重要。
至少掌握中序的迭代版本——面试官经常追问。
提到 Morris 遍历（O(1) 空间）可以加分。
将遍历顺序与实际问题关联：中序验证 BST，前序克隆树。
三种遍历都是 O(n)，因为每个节点恰好被访问一次。
前序遍历适合复制树或将树序列化为扁平结构以便存储。
层序遍历（BFS）使用队列逐层访问节点，与三种深度优先遍历不同。