二叉树的层序遍历-102
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res; // 二维数组用来存储每层节点
if (root == nullptr)
return res;
queue<TreeNode*> q; // 队列用来进行层序遍历
q.push(root); // 将第一层的根节点加入队列中
while (!q.empty()) {
int n = q.size(); // 当前层的节点个数
vector<int> vec; // 用于存储当前层的所有节点
for (int i = 1; i <= n; i++) {//遍历当前层的所有节点
TreeNode* node = q.front();//将队列当前节点存下来
q.pop();//将当前节点弹出队列
vec.push_back(node->val);//将存下来的当前节点
if (node->left)q.push(node->left);//如果当前节点有左节点，加入队列
if (node->right)q.push(node->right);//如果当前节点有右节点，加入队列
}
res.push_back(vec);//将当前层的节点值加入结果
}
return res;
}
};什么是 C++ 中的函数对象？它有什么特点？函数对象与普通函数有什么区别？ 如何定义和使用函数对象？
C++ 中的函数对象（Function Object）
函数对象（又称为函数符号）是一个可以像普通函数一样被调用的对象。在 C++ 中，函数对象是通过重载 operator() 来实现的。它的本质上是一个类的实例，而该类的实例具有函数调用的能力。因此，函数对象可以像普通函数一样在代码中传递和调用。
函数对象的特点
1.像函数一样调用：
函数对象是通过重载 operator() 来实现的，它使得该对象能够像函数一样被调用。
2.可以有状态：
函数对象与普通函数的最大区别是，函数对象可以拥有成员变量（即状态）。这使得它在多次调用时可以保持和修改状态。
3.可以传递给算法：
函数对象可以作为参数传递给 C++ 标准库中的算法（如 std::sort、std::for_each 等），并且由于它们是对象，可以在调用时携带更多的上下文信息。
4.性能：
函数对象通常可以通过内联优化，从而提高性能，特别是与普通函数指针相比，它们能更好地支持编译器优化。
5.支持多态：
函数对象可以通过继承和多态进行扩展，支持不同的行为和策略模式。
函数对象与普通函数的区别
如何定义和使用函数对象
1. 定义函数对象
要定义一个函数对象，需要：
创建一个类。
在类中重载 operator() 方法，使对象能够像函数一样调用。
#include <iostream>
using namespace std;
// 定义一个函数对象
class Add {
public:
int operator()(int x, int y) {
return x + y; // 重载 operator() 实现加法操作
}
};
int main() {
Add add; // 创建函数对象
cout << add(2, 3) << endl; // 调用函数对象，相当于调用 add.operator()(2, 3)
return 0;
}
输出：
5
2. 使用函数对象作为参数
函数对象可以作为参数传递给 C++ 标准库中的算法，像是 std::for_each、std::sort 等。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 函数对象：加法操作
class Add {
public:
void operator()(int x) {
cout << x + 10 << " "; // 每个元素加 10
}
};
int main() {
vector<int> nums = {1, 2, 3, 4, 5};
// 使用函数对象作为参数
for_each(nums.begin(), nums.end(), Add());
return 0;
}
输出：
11 12 13 14 15
3. 函数对象作为排序准则
函数对象也可以用于自定义排序准则，比如与 std::sort 一起使用：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 函数对象：比较两个整数的大小
class Compare {
public:
bool operator()(int x, int y) {
return x > y; // 降序排列
}
};
int main() {
vector<int> nums = {5, 1, 8, 3, 7};
// 使用函数对象作为排序准则
sort(nums.begin(), nums.end(), Compare());
// 打印排序后的结果
for (int num : nums) {
cout << num << " ";
}
return 0;
}
输出：
8 7 5 3 1
4. 函数对象的带状态
函数对象不仅仅能执行操作，还可以保存一些状态，下一次调用时可以利用这些状态。
#include <iostream>
using namespace std;
// 函数对象：加法器，带状态
class Adder {
private:
int sum = 0; // 存储状态
public:
void operator()(int x) {
sum += x; // 修改状态
cout << "Current sum: " << sum << endl;
}
};
int main() {
Adder add;
add(10); // sum = 10
add(20); // sum = 30
add(30); // sum = 60
return 0;
}
输出：
Current sum: 10
Current sum: 30
Current sum: 60
在这个例子中，Adder 类通过一个成员变量 sum 来保存当前的总和，每次调用 operator() 时都会修改这个状态。
函数对象的应用场景
1.算法：
C++ 标准库中有很多算法（如 std::for_each, std::sort, std::transform 等）都可以使用函数对象进行定制化操作。例如，使用函数对象作为排序准则，或者用作算法中的自定义操作。
2.回调机制：
函数对象可以用来实现回调机制，它们的状态可以保存更多上下文信息，因此比普通函数更灵活。
3.自定义操作：
需要在运行时根据某些条件定制化操作时，函数对象比普通函数更加灵活。通过在类中保存状态和行为，函数对象可以实现更复杂的行为。
总结
函数对象 是可以像普通函数一样被调用的类实例，通过重载 operator() 来实现。
函数对象的优势：除了能像普通函数一样调用，它们还能拥有状态，并且能够灵活扩展，使得代码更具可读性和可扩展性。
与普通函数的区别：函数对象不仅可以像普通函数一样执行操作，还能够保存和改变状态，支持多态性和灵活性。
应用：函数对象广泛应用于 C++ 标准库算法（如排序、遍历等）中，能够提供定制化的操作。