第3课：前序与中序遍历
进度 0/24
🚶
前序与中序遍历
三种脚步走遍一棵树，离信奥更近一步！
📖知识引入
🥇前序遍历
根→左→右，先访问自己再访问孩子，像先自我介绍
🥈中序遍历
左→根→右，根夹在中间，对二叉搜索树正好输出升序
🔁递归实现
遍历左右子树就是同样问题的缩小版，天然适合递归
🧩还原一棵树
前序序列找根，中序序列按根分左右，两序联手能还原整棵树
💡
前序的第一个节点一定是根；中序里根左边的节点全在左子树，右边全在右子树
🔍前序与中序遍历函数
void preorder(TreeNode* root) { // 前序：根左右
if (root == nullptr) return;
cout << root->val << " "; // 先访问根
preorder(root->left);
preorder(root->right);
}
void inorder(TreeNode* root) { // 中序：左根右
if (root == nullptr) return;
inorder(root->left);
cout << root->val << " "; // 根夹在中间
inorder(root->right);
}两个函数只差一行输出位置，输出语句放的位置决定遍历顺序。
🎯小测验
第1题：前序遍历的访问顺序是？
第2题：中序遍历的访问顺序是？
第3题：前序遍历序列的第一个节点是？
📝本课知识点
- ✓前序=根左右
- ✓中序=左根右
- ✓树的遍历天然适合递归
第3课完成！继续探索下一课吧 🚀