第4课：后序遍历与层序遍历
进度 0/24
🌊
后序遍历与层序遍历
一条队列，让树一层层现形！
📖知识引入
🥉后序遍历
左→右→根，先处理孩子再处理自己，统计子树信息必用它
🌊层序遍历
一层一层、从左到右访问，像给树拍全身照
🔄队列驱动
根先入队，出队一个点就把它的孩子依次入队，循环到队空
💡怎么选
自底向上统计用后序，逐层处理、找最短层数用层序
💡
层序遍历的队列变空之前，最后一个出队的节点一定在 deepest 那一层
🔍用queue实现层序遍历
#include <queue>
using namespace std;
void levelOrder(TreeNode* root) {
queue<TreeNode*> q;
q.push(root); // 根先入队
while (!q.empty()) {
TreeNode* cur = q.front(); q.pop();
cout << cur->val << " ";
if (cur->left) q.push(cur->left); // 左孩子先入队
if (cur->right) q.push(cur->right);
}
}出队访问，左右孩子依次入队，队列空了整棵树就走完了。
🎯小测验
第1题：后序遍历的访问顺序是？
第2题：层序遍历要借助什么数据结构？
第3题：层序遍历中节点的孩子何时入队？
📝本课知识点
- ✓后序=左右根
- ✓层序=队列+逐层访问
- ✓层序遍历是BFS的雏形
第4课完成！继续探索下一课吧 🚀