力扣 二叉树的层序遍历-102

发布于:2024-11-29 ⋅ 阅读:(33) ⋅ 点赞:(0)

二叉树的层序遍历-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++ 标准库算法(如排序、遍历等)中,能够提供定制化的操作。