算法：二叉树遍历
遍历：根序，左永远在右的前面
从下到上：后序，从上到下：先序，有序输出二叉树：中序（落下顺序）
遍历（Traversal）
│
├─ DFS（深度优先）
│ ├─ 前序
│ ├─ 中序
│ └─ 后序
│
└─ BFS（广度优先）
└─ 层序
层序
先把一层的节点放进队列，
遍历这一层，
同时把这一层的子节点放进队列，
通过控制 size 决定是否是当前层的节点
👉 标准写法就是：
queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();// 当前层节点数for(inti=0;i<size;i++){Nodecur=queue.poll();// 当前层节点process(cur);if(cur.left!=null)queue.offer(cur.left);if(cur.right!=null)queue.offer(cur.right);}// 到这里：一整层处理完}30 秒遍历选择法（面试 / 刷题通用）
你只需要问 3 个问题，按顺序来。
✅ 第 1 问（最重要）
当前节点的结果，是否依赖子节点的结果？
换句话说： “我必须先知道孩子的情况，才能决定自己吗？” ✔️ 如果是 → 后序遍历（自底向上） ❌ 如果不是 → 继续问第2问 典型题目特征 删除目录/删除节点 计算高度、大小、最大路径和 判断是否为叶子 DP on tree 📌 你这道“删除目录”题，一句话就能命中这一问✅ 第 2 问
我是否需要在“刚到这个节点”时就做事？ 比如： 初始化 打印路径 把父节点的信息传给子节点 ✔️ 如果是 → 前序遍历（从头到尾） ❌ 如果不是 → 继续问第3问 典型题目特征 打印目录结构 路径和（从根到叶） 序列化树 拷贝树✅ 第 3 问（基本只剩一种）
是否需要“左 → 中 → 右”的顺序性质？ 一般只在 二叉搜索树 出现 ✔️ 是 → 中序遍历 ❌ 否 → 回到前序/后序中重新审视 📌 目录树、N叉树99%不用中序 🔥 一句话速记版（建议背） 用不用孩子的结果 → 后序 进门就干活 → 前序 要有序 → 中序 题1：删除目录（你已经做过） 给一棵目录树，只能删除叶子目录； 子目录删完后，父目录可能变成叶子并继续删除。✅ 正确遍历
后序遍历
📌 判断一句话：
父目录是否可删，取决于子目录是否已删完 → 依赖子节点结果
题 2：计算一棵树的高度
树的高度定义为：
max(左子树高度, 右子树高度) + 1
✅ 正确遍历
后序遍历
📌 判断一句话：
当前节点的高度，必须等子树高度算完
题 3：打印目录结构（类似 tree 命令）
按层级打印所有目录名
✅ 正确遍历
前序遍历
📌 判断一句话：
一到节点就要打印，再处理子目录
题 4：判断一棵树是否是平衡二叉树
每个节点左右子树高度差 ≤ 1
✅ 正确遍历
后序遍历
📌 判断一句话：
是否平衡，取决于左右子树高度
题 5：输出二叉搜索树的升序序列
BST：左 < 根 < 右
✅ 正确遍历
中序遍历
📌 判断一句话：
只有中序才能保证有序输出
题 6：统计从根到叶子的所有路径
输出类似：A->B->C
✅ 正确遍历
前序遍历
📌 判断一句话：
路径信息要在“进入节点时”就加入
题 7：计算每个目录的总文件大小
目录大小 = 所有子目录大小 + 本目录文件大小
✅ 正确遍历
后序遍历
📌 判断一句话：
父目录大小依赖子目录大小
题 8：复制一棵树（深拷贝）
生成一棵结构和值完全一样的新树
✅ 正确遍历
前序遍历
📌 判断一句话：
必须先创建父节点，才能挂子节点
题 9：判断是否存在一条根到叶子的路径和等于 target
经典 Path Sum 题
✅ 正确遍历
前序遍历
📌 判断一句话：
累加路径和是在“向下走”的过程中完成的
题 10：求一棵树的最大路径和（可不经过根）
LeetCode Hard 级别
✅ 正确遍历
后序遍历
📌 判断一句话：
当前节点能提供的最大贡献，来自左右子树结果
🎯 你应该得到的“条件反射”
如果你现在回看这 10 题，发现：
后序遍历：凡是“算 / 判断 / 汇总 / 删除”
前序遍历：凡是“记录 / 传递 / 打印 / 构建”
中序遍历：几乎只在 BST 的“有序性”
👉 那说明你已经真的掌握了遍历选择
🧠 终极 30 秒判断口诀（压轴）
要结果 → 等孩子 → 后序
要过程 → 先自己 → 前序
要顺序 → BST → 中序