二叉树遍历 · 单步演示
中序遍历
先中序遍历左子树，再访问根，最后中序遍历右子树。对二叉搜索树做中序遍历，得到的正好是从小到大的序列。
调用栈（底 → 顶）（空）
中序序列（空）
步 001 / 057中序遍历：先左子树，再访问根，最后右子树。
键盘：← → 单步，空格 播放/暂停（先点一下演示区）。
伪代码 · 当前行高亮
遍历(node)：if node 为空：return遍历(node.left)访问 node遍历(node.right)
变量
| node | 空 |
|---|---|
| 递归深度 | 0 |
| 已输出 | [] |
复杂度
| 最好情况 | O(n) |
|---|---|
| 平均情况 | O(n) |
| 最坏情况 | O(n) |
| 额外空间 | O(h) |
每个结点访问一次；调用栈深度等于树高 h。
要点
- 默认输入是一棵二叉搜索树，中序结果是递增的，可以用来检查一棵树是不是二叉搜索树。
- 在中序序列里，根把序列分成左子树和右子树两段。
常见错误
把「访问」写在两个递归调用之前或之后，就变成了前序或后序——三种遍历的区别只在这一行的位置。