算法之二叉树

102. 二叉树的层序遍历 - 力扣（LeetCode）

一 DFS和BFS

1.1 DFS

#include <iostream>// 二叉树节点的定义
struct TreeNode {int val;               // 节点值TreeNode *left;        // 左子树指针TreeNode *right;       // 右子树指针// 构造函数TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};// DFS遍历函数（后序遍历：先左子树，再右子树）
void dfs(TreeNode* root) {if (root == nullptr) {  // 若节点为空，直接返回return;}dfs(root->left);        // 递归遍历左子树dfs(root->right);       // 递归遍历右子树// 此处可添加对当前节点的处理逻辑，如：// std::cout << root->val << " ";
}

1.2 BFS

// BFS遍历函数（层序遍历）
void bfs(TreeNode* root) {if (root == nullptr) {  // 处理空树情况return;}std::queue<TreeNode*> queue;  // C++中使用std::queue，存储节点指针queue.push(root);             // 将根节点入队while (!queue.empty()) {      // 队列不为空时循环TreeNode* node = queue.front();  // 获取队首元素（C++的front()对应Java的peek()）queue.pop();                     // 移除队首元素（C++的pop()仅移除不返回，对应Java的poll()）// 处理当前节点（根据需求添加逻辑，如打印节点值）// std::cout << node->val << " ";// 左子节点不为空则入队if (node->left != nullptr) {queue.push(node->left);}// 右子节点不为空则入队if (node->right != nullptr) {queue.push(node->right);}}
}

二 二叉树层序遍历

class Solution {
public:std::vector<std::vector<int>> levelOrder(TreeNode* root) {std::vector<std::vector<int>> res;  // 存储最终结果if (root == nullptr) {  // 空树直接返回空结果return res;}std::queue<TreeNode*> q;  // 队列用于存储待处理的节点q.push(root);             // 根节点入队while (!q.empty()) {int n = q.size();  // 当前层的节点数量std::vector<int> level;  // 存储当前层的节点值// 处理当前层的所有节点for (int i = 0; i < n; ++i) {TreeNode* node = q.front();  // 获取队首节点q.pop();                     // 移除队首节点level.push_back(node->val);  // 将当前节点值加入当前层// 左子节点不为空则入队if (node->left != nullptr) {q.push(node->left);}// 右子节点不为空则入队if (node->right != nullptr) {q.push(node->right);}}res.push_back(level);  // 将当前层加入结果集}return res;
}
};

【1】将当前层的node全部弹出，q.front()

【2】res是vector<vetor<int>>，每一层用一个vector<int>装