虾皮C++后端开发一面

公众号：阿Q技术站

来源：https://www.nowcoder.com/feed/main/detail/c9b2920227bd441a9da97ca5da4d567d

简历上写的是c++，但面试官估计是Java的，一上来问我会不会Java，我说了会，他问了几个问题后，有些没答上来，就没有继续为难我。然后开启八股的轰炸。

1、面向对象？

看题主这里只写了面向对象，我还是给大家将面向过程和面向对象区分一下吧。

1. 面向过程？

   • 分析出解决问题所需要的步骤，然后用函数把这些步骤一步一步实现，使用的时候一个一个依次调用就可以了。

   • 优点：性能比面向对象高，因为类调用时需要实例化，开销比较大，比较消耗资源;比如单片机、嵌入式开发、 Linux/Unix等一般采用面向过程开发，性能是最重要的因素。 缺点：没有面向对象易维护、易复用、易扩展。

2. 面向对象

• 把构成问题事务分解成各个对象，建立对象的目的不是为了完成一个步骤，而是为了描述某个事物在整个解决问题的步骤中的行为。

• 优点：易维护、易复用、易扩展，由于面向对象有封装、继承、多态性的特性，可以设计出低耦合的系统，使系统更加灵活、更加易于维护。 缺点：性能比面向过程低。

2、面向对象的特征？

1. 封装：

   • 封装是OOP的基本特征之一。
   • 允许将数据（成员变量）和方法（成员函数）组合到一个单元中，这个单元称为类。
   • 类的成员变量通常是私有的，只能通过公共接口（成员函数）访问。
   • 封装提供了数据隐藏和隔离，可以避免直接访问和修改对象的内部状态。

2. 继承：

   • 继承允许创建一个新的类，基于现有类的属性和行为。
   • 派生类（子类）可以继承父类的成员变量和方法。
   • 继承支持代码重用，使得可以构建层次结构的类。

3. 多态：

   • 多态性允许对象在不同情况下表现出不同的行为。
   • C++实现多态性主要通过函数重载和虚函数。
   • 函数重载允许在同一类中定义多个同名函数，根据参数的不同选择合适的函数。
   • 虚函数允许在派生类中重写父类的方法，实现运行时多态。

4. 抽象类和纯虚函数：

   • C++支持抽象类，这是不能被实例化的类，通常用于定义接口。
   • 抽象类中可以包含纯虚函数，这是没有实现的虚函数，派生类必须实现它们。

5. 类和对象：

   • C++中，类是一种用户自定义的数据类型，用于描述对象的属性和行为。
   • 对象是类的实例，它可以访问类的成员变量和方法。

6. 构造函数和析构函数：

   • 构造函数用于初始化对象的成员变量。
   • 析构函数用于清理对象所分配的资源。

7. 访问控制：

   • C++中，成员变量和成员函数可以具有不同的访问权限，包括公有（public）、私有（private）和受保护（protected）。
   • 公有成员可以被类外部和派生类访问。
   • 私有成员只能被类内部访问。
   • 受保护成员可以被类内部和派生类访问。

8. 操作符重载：

   C++允许操作符重载，使得用户可以自定义操作符的行为。

3、Java中多态的实现和作用？

在Java中，多态的实现和作用主要依赖于以下几个特性：

1. 方法重写（Method Overriding）：
   • 多态的基础是方法重写。在Java中，子类可以重写（覆盖）父类的方法，前提是子类的方法具有与父类相同的名称、参数列表和返回类型。
   • 当父类引用指向子类对象时，通过这个引用调用方法时，实际会调用子类的方法，这就实现了多态。
2. 向上转型（Upcasting）：
   • 向上转型是多态的一种表现形式，它允许将子类对象赋值给父类引用。
   • 通过向上转型，可以实现将不同的子类对象当做父类对象来处理，从而提高代码的灵活性。
3. 抽象类和接口：
   • Java中的抽象类和接口也支持多态。
   • 抽象类可以包含抽象方法，派生类必须实现这些抽象方法，从而实现多态。
   • 接口定义了一组抽象方法，类可以实现接口，通过接口来实现多态。

多态的作用和优势：

• 代码的通用性和灵活性：多态允许在不同子类间共享通用的父类引用，从而提高代码的通用性和复用性。
• 简化代码：通过多态，可以编写更加通用的代码，减少重复性代码的编写。
• 降低耦合性：多态降低了代码的耦合性，允许将不同类的对象视为同一类型的对象，减少了依赖具体实现的程度。

例子：

class Animal {
    void makeSound() {
        System.out.println("Some sound");
    }
}

class Dog extends Animal {
    @Override
    void makeSound() {
        System.out.println("Bark");
    }
}

class Cat extends Animal {
    @Override
    void makeSound() {
        System.out.println("Meow");
    }
}

public class Main {
    public static void main(String[] args) {
        Animal myDog = new Dog();
        Animal myCat = new Cat();

        myDog.makeSound();  // 输出 "Bark"
        myCat.makeSound();  // 输出 "Meow"
    }
}

4、Java中继承和多态的区别？

5、Java中抽象类和接口之间的区别？

抽象类（Abstract Class）：

• 抽象类可以包含抽象方法（方法没有实现），也可以包含具体方法（方法有实现）。
• 抽象类可以有成员变量，可以有构造方法，可以拥有普通方法。
• 一个类只能继承一个抽象类，即Java不支持多重继承。
• 抽象类用abstract关键字定义，使用extends关键字来继承。

abstract class Shape {
    // 抽象方法
    public abstract void draw();
    
    // 具体方法
    public void move() {
        System.out.println("Moving the shape");
    }
}

接口（Interface）：

• 接口只包含抽象方法（方法没有实现），没有成员变量，没有构造方法。
• 一个类可以实现多个接口，支持多接口继承。
• 接口用interface关键字定义，使用implements关键字来实现。

interface Drawable {
    // 抽象方法
    void draw();
}

interface Movable {
    // 抽象方法
    void move();
}

6、数据库事物的隔离级别及每种隔离级别的使用场景？

从最低到最高分别是：

1. 读未提交（Read Uncommitted）：在这个隔离级别下，一个事务可以读取另一个事务尚未提交的修改，可能导致脏读、不可重复读和幻读问题。这个隔离级别通常用于极少需要数据一致性的场景。
2. 读已提交（Read Committed）：这是大多数数据库的默认隔离级别。在这个级别下，一个事务只能读取已经提交的其他事务的数据。这可以避免脏读，但仍然允许不可重复读和幻读。
3. 可重复读（Repeatable Read）：在这个隔离级别下，一个事务在读取数据时，其他事务无法修改这些数据，因此不可重复读问题被解决。但仍然可能存在幻读问题，因为其他事务可以插入新数据。
4. 串行化（Serializable）：这是最高的隔离级别，它确保了最高的数据完整性，避免了所有类型的并发问题，包括脏读、不可重复读和幻读。这通常是通过锁定数据来实现的，因此可能导致性能问题，不适用于高并发系统。

使用场景：

• 读未提交：极少需要数据一致性的场景，对性能要求较高，可以容忍脏读的情况。
• 读已提交：大多数应用的默认隔离级别，适用于大多数应用场景，具有良好的性能和数据一致性。
• 可重复读：需要更高一致性，但可以容忍轻微的性能损失的场景，适用于大部分企业级应用。
• 串行化：对数据一致性要求最高，可以容忍较低的性能，适用于少数需要最高数据保护的场景，如金融系统。

7、数据库的索引及数据结构？

1. B-树索引：B-树（或B+树）是最常见的数据库索引结构。它是一种自平衡的树，用于存储有序数据。B-树索引适用于范围查询和等值查询，并且在各种数据库管理系统中得到广泛支持。
2. 哈希索引：哈希索引使用哈希函数将索引键映射到一个固定大小的散列地址，因此它适用于等值查询。哈希索引对于等值查询的性能非常出色，但不适用于范围查询。
3. 位图索引：位图索引是一种用于标记记录是否存在于索引键的索引结构。它适用于列中的不同值有限的情况，如性别、国家等。位图索引可以在多个位图上进行位运算，用于复杂的条件查询。
4. 全文索引：全文索引主要用于处理文本数据。它支持全文搜索和自然语言查询，允许用户查找文本数据中的关键词和短语。
5. 空间索引：空间索引用于地理信息系统（GIS）等应用中，支持地理空间数据的检索和查询。
6. 唯一索引：唯一索引确保索引键的值是唯一的，用于实施唯一性约束。它通常在主键和唯一性约束字段上创建。
7. 复合索引：复合索引包含多个列，以支持多个列的查询。这可以提高多列条件查询的性能。
8. 聚簇索引：聚簇索引决定了数据在表中的物理存储顺序。在大多数数据库中，主键索引通常是聚簇索引。

8、数据库事物的特性？

1. 原子性：原子性要求事务是一个不可分割的操作单元，要么完全执行，要么完全不执行。这意味着如果事务中的任何一部分操作失败，整个事务都会被回滚到初始状态，以保持数据的一致性。原子性确保了数据库在并发操作中的数据完整性。
2. 一致性：一致性确保事务将数据库从一个一致性状态转变为另一个一致性状态。这意味着事务在执行前后必须遵守预定义的业务规则，以确保数据的完整性。如果事务执行成功，数据库状态应该符合事务执行后的预期状态。
3. 隔离性：隔离性定义了多个并发事务之间的相互隔离程度。它确保一个事务的执行不会受到其他并发事务的影响。高度隔离的事务可以减少并发操作引发的问题，但也可能导致性能下降。SQL标准定义了四种隔离级别：读未提交（Read Uncommitted）、读提交（Read Committed）、可重复读（Repeatable Read）和串行化（Serializable）。
4. 持久性：持久性要求一旦事务成功提交，其结果应该永久保存在数据库中，即使系统故障或重启后也不应丢失。通常，数据库系统通过将事务日志持久化到磁盘来实现持久性。

9、如何查看计算机的内存使用情况？

使用 top 命令：

top 命令提供了实时的系统监视信息，包括内存使用情况。

top 命令将显示实时的系统性能信息。在顶部的部分，你可以看到内存信息，包括总内存、已用内存、空闲内存、缓存和缓冲区内存。这些信息以千字节（KB）为单位，并在不断更新。

使用 free 命令：

free 命令用于显示系统内存使用情况的摘要信息。

free 命令将显示内存信息的摘要，包括总内存、已用内存、空闲内存、缓存和缓冲区内存。这些信息以千字节（KB）为单位，并显示在一个静态输出中，而不是实时更新。

区别：

• top 提供了更详细的系统性能信息，而不仅仅是内存。它还允许你监视正在运行的进程和 CPU 使用情况等。
• free 提供了内存信息的静态摘要，适用于快速查看内存情况。

10、如何查看进程？

使用 ps 命令：

ps -aux | grep 进程名
ps -ef | grep 进程号

11、线程的同步机制及锁的介绍和应用？

1. 互斥锁（Mutex）： 互斥锁是最基本的线程同步机制，用于保护共享资源，确保一次只有一个线程可以访问被锁定的资源。线程在访问共享资源之前会尝试获取锁，如果锁已被其他线程占用，线程将被阻塞，直到锁可用。一旦线程完成操作，它会释放锁，允许其他线程访问。
2. 信号量（Semaphore）： 信号量是一种更通用的同步机制，用于控制对一组资源的访问。它可以允许多个线程同时访问资源，但受信号量的计数限制。信号量的计数可以增加或减少，线程可以等待信号量达到特定值或等待资源释放。
3. 条件变量（Condition Variable）： 条件变量通常与互斥锁一起使用，用于在线程之间进行协调和通信。一个线程可以在条件变量上等待某个条件的发生，而其他线程可以在满足条件时通知等待线程。条件变量在典型情况下用于线程的等待和唤醒操作。
4. 读写锁（Read-Write Lock）： 读写锁用于控制对共享资源的并发访问。多个线程可以同时读取共享资源，但只有一个线程可以写入。这提高了并发性，因为多个线程可以同时读取，但写入是互斥的。
5. 自旋锁（Spin Lock）： 自旋锁是一种无阻塞锁，线程在尝试获取锁时会一直自旋，直到锁可用。自旋锁适用于短期等待，不适合长时间的等待。

锁的应用场景：

1. 共享资源保护： 最常见的用途是保护共享资源，例如数据结构、文件、网络连接等，以确保多个线程不会同时访问导致数据损坏或不一致。
2. 线程安全性： 在多线程编程中，确保线程安全是至关重要的。锁用于协调多个线程的访问，以防止竞态条件和数据争用。
3. 任务调度： 锁可以用于任务调度，例如线程池中的任务队列。锁用于确保任务队列的同步访问，以避免多个线程同时访问任务队列。
4. 缓存同步： 在缓存应用中，锁可以用于确保多个线程对缓存的读取和写入操作不会导致数据不一致或并发问题。
5. 生产者-消费者问题： 锁经常用于解决生产者-消费者问题，确保生产者和消费者之间的协调和同步。
6. 并发算法： 在并发编程中，锁用于实现各种并发算法，例如并发队列、并发映射和并发数据结构。
7. 线程间通信： 锁通常与条件变量结合使用，以实现线程之间的通信和等待通知机制。

12、如何预防和解决死锁？

预防死锁的方法：

1. 使用互斥锁和资源分配策略： 使用互斥锁来确保一次只有一个线程可以访问共享资源，并实施合理的资源分配策略，以避免资源争用。
2. 避免持有多个锁： 尽量避免一个线程同时持有多个锁，因为这增加了死锁的可能性。如果必须使用多个锁，请确保以相同的顺序获取和释放锁。
3. 使用超时机制： 在获取锁时，可以设置一个超时时间，如果在规定时间内无法获取锁，线程可以释放已经获取的锁并重试，以避免死锁。
4. 避免循环等待： 设计资源分配策略，以避免循环等待的情况发生。例如，可以规定线程只能按顺序获取资源，而不是尝试同时获取多个资源。

解决死锁的方法：

1. 检测和恢复： 实施死锁检测算法，以检测死锁的发生。一旦检测到死锁，可以采取恢复措施，如终止其中一个或多个死锁线程，以解除死锁。
2. 资源分配撤销： 如果系统支持，可以实施资源分配撤销策略，即当检测到死锁时，释放某些资源以解锁死锁。
3. 等待-通知机制： 使用条件变量和等待-通知机制来协调线程的执行。线程可以等待特定条件的发生，而其他线程可以通知它们条件已满足。
4. 资源分配有序性： 定义资源的分配和释放的有序性，以确保线程按照相同的顺序获取和释放资源，以避免循环等待。
5. 锁超时和重试： 设置锁的超时时间，如果无法获取锁，线程可以释放已获取的锁并重试，以避免死锁。
6. 避免阻塞： 尽量减少线程的阻塞时间，避免在临界区内执行长时间的操作，以降低死锁的概率。

13、常见协议端口号？

1. HTTP：80（HTTP）和443（HTTPS）。
   • 80端口用于HTTP通信，通常是未加密的。
   • 443端口用于HTTPS通信，加密的HTTP通信。
2. FTP ：21（控制连接）和20（数据连接）。
   • 21端口用于FTP的控制连接，用于命令和控制操作。
   • 20端口用于FTP的数据连接，用于实际文件传输。
3. SSH ：22端口用于安全的远程登录和文件传输。
4. SMTP：25端口用于发送电子邮件。
5. POP3：110端口用于接收电子邮件。
6. IMAP：143端口也用于接收电子邮件，但提供了更多的功能和灵活性。
7. DNS：53端口用于域名解析，将域名映射到IP地址。
8. Telnet：23端口用于远程终端连接，通常是明文传输。
9. SMTPS：465端口用于通过加密通信的SMTP。
10. SNMP：161（SNMP）和162（SNMP Trap）。
    • 161端口用于SNMP通信，允许管理和监视网络设备。
    • 162端口用于SNMP陷阱，用于通知管理站点的事件。
11. HTTP Proxy： 3128（常见代理端口）端口通常用于HTTP代理服务器。
12. RDP (Remote Desktop Protocol)：3389端口用于远程桌面连接。

14、RPC协议？

RPC（远程过程调用）是一种协议，允许一个程序在网络上请求另一个程序或计算机上的函数或过程（通常称为远程服务器）执行，就像调用本地函数一样。RPC协议用于实现分布式系统和跨网络通信，允许远程计算机之间的数据交换和协作。

1. 远程调用：RPC允许一个计算机上的应用程序调用另一台计算机上的函数或过程，就好像它们在同一台计算机上运行一样。这些函数可以接受参数并返回结果。
2. 网络通信：通过网络进行通信，通常使用TCP/IP协议栈或其他网络协议。这使得远程计算机能够相互通信。
3. 序列化和反序列化：在RPC调用中，参数和结果需要在网络上传输。因此，它们需要被序列化（编码为字节流）并在目标计算机上被反序列化（解码为数据）。这确保了数据的正确传输。
4. 协议定义：RPC协议需要明确定义可调用函数的接口，包括函数的名称、参数和返回值。通常使用IDL或其他接口描述语言来定义接口。
5. 多语言支持：RPC协议通常支持多种编程语言，因此可以实现跨语言的远程调用。
6. 通信模式：RPC可以采用同步或异步通信模式。在同步模式下，调用方会等待远程调用的完成并返回结果。在异步模式下，调用方可以继续执行其他任务，而不必等待结果返回。

15、TCP的三次握手和四次挥手？

三次握手

1. 第一次握手： 客户端发送一个TCP报文段，其中包含一个SYN（同步）标志位，以及客户端的初始序列号（ISN，Initial Sequence Number）。这表示客户端请求建立连接，并设置了初始序列号，以便后续的数据传输。
2. 第二次握手： 服务器接收到客户端的SYN后，确认收到，并发送回一个带有SYN和ACK（确认）标志位的报文段。服务器也会为自己设置一个初始序列号。
3. 第三次握手： 客户端接收到服务器的SYN-ACK后，确认收到，并发送一个ACK标志位的报文段。这个报文段表示连接已经建立，双方可以开始进行数据传输。

此时，TCP连接已经建立，双方可以安全地传输数据。

四次挥手

1. 第一次挥手： 当客户端完成了数据传输后，它会发送一个FIN标志位的报文段，表示它不再有数据要发送，但仍然愿意接收数据。客户端进入FIN_WAIT_1状态。
2. 第二次挥手： 服务器接收到客户端的FIN后，确认收到，并发送一个ACK标志位的报文段。此时，服务器可以继续向客户端发送数据。
3. 第三次挥手： 当服务器也完成了数据传输后，它会发送一个FIN标志位的报文段，表示它不再有数据要发送。服务器进入CLOSE_WAIT状态，等待客户端的确认。
4. 第四次挥手： 客户端接收到服务器的FIN后，确认收到，并发送一个ACK标志位的报文段。客户端进入TIME_WAIT状态，等待可能出现的服务器重传。

在TIME_WAIT状态等待一段时间后，客户端和服务器都可以关闭连接。整个四次挥手过程确保双方都完成了数据传输并关闭了连接。

16、HTTP和TCP的关系和区别？

关系：

1. HTTP建立在TCP之上： HTTP是一个应用层协议，而TCP是传输层协议。HTTP通常使用TCP作为它的传输层协议，以在网络上传输数据。HTTP与TCP之间的关系可以类比为在实体之上建立一个通信通道。
2. HTTP利用TCP的可靠性： TCP提供了可靠的、面向连接的数据传输。HTTP利用TCP的可靠性来确保数据的正确传递，包括数据的分段和重新组装、错误检测和重传等。

区别：

1. 层次： TCP是传输层协议，负责在两台计算机之间建立连接、可靠地传输数据流，以及处理数据分段和重传等传输细节。HTTP是应用层协议，负责定义数据的格式和如何在客户端和服务器之间传输数据。
2. 功能： TCP关注于数据传输的可靠性和流控制，而HTTP关注于定义如何呈现和传输文档、图像、视频等内容。HTTP通过请求-响应模型允许客户端请求网络资源，并服务器响应这些请求。
3. 端口： TCP使用端口来标识不同的应用程序或服务，允许多个不同的应用程序在同一台计算机上共享网络连接。HTTP默认使用TCP端口80（HTTP）或443（HTTPS）。
4. 通信模式： TCP是一种点对点的通信协议，即两台计算机之间的通信。HTTP是一种客户端-服务器通信模式，客户端发送请求，服务器返回响应。
5. 状态： TCP是无状态的协议，它不保留关于连接的持久状态信息。HTTP也是无状态的，每个HTTP请求和响应之间是相互独立的，不保留客户端之间的状态。

17、HTTP和HTTPS的关系和区别？

HTTPS是HTTP的安全版本，两者都用于在客户端和服务器之间传输数据，但HTTPS添加了加密和安全性层，以保护数据的机密性和完整性。

区别：

1. 安全性：

   • HTTP：HTTP是一种不安全的协议，数据在传输过程中以明文形式传输，容易受到窃听和篡改的风险。
   • HTTPS：HTTPS通过使用加密机制（通常是TLS/SSL）来保护数据的机密性，使数据在传输过程中加密，从而提供更高的安全性。

2. 端口：

   • HTTP：HTTP默认使用端口80进行通信。
   • HTTPS：HTTPS默认使用端口443进行通信。

3. 加密：

   • HTTP：HTTP不提供加密，数据可以在网络上传输时被窃听。
   • HTTPS：HTTPS使用TLS/SSL协议进行数据加密和解密，确保数据在传输过程中的保密性。

4. 证书：

   • HTTP：HTTP不涉及数字证书的使用。
   • HTTPS：HTTPS需要服务器获得数字证书，并由权威的证书颁发机构（CA）签发，以验证服务器的身份。客户端可以使用证书来确保它们正在连接到合法的服务器。

5. 认证和身份验证：

   • HTTP：HTTP不提供身份验证机制，任何人都可以发送HTTP请求。
   • HTTPS：HTTPS提供了对服务器和（可选）客户端的身份验证，确保双方的合法性。

6. SEO（搜索引擎优化）：

   HTTP：搜索引擎可能更喜欢使用HTTPS的网站，因为它们提供了更高的安全性，可以影响搜索排名。

18、对称加密算法及常见的算法名称？

对称加密算法是一种加密技术，它使用相同的密钥（称为密钥）用于加密和解密数据。以下是一些常见的对称加密算法及其名称：

1. DES：DES是一种早期的对称加密算法，使用56位密钥进行加密。由于密钥长度较短，它已经不再被视为安全的加密方法，通常被更强大的算法替代。
2. 3DES：3DES是DES的增强版本，使用三个56位密钥进行加密。虽然它比DES更强大，但由于其较长的密钥，它的性能相对较低。
3. AES：AES是一种现代的对称加密算法，广泛用于加密和解密数据。它支持128位、192位和256位密钥长度，被认为是高度安全的加密算法。
4. RC4：RC4是一种流密码算法，它可以使用不同长度的密钥。尽管它曾经广泛用于加密通信，但由于存在一些安全问题，现在不再被推荐使用。
5. Blowfish：一种块密码算法，支持不同长度的密钥，通常被用于数据加密和虚拟私人网络（VPN）等应用。
6. SEAL：SEAL是一种高度安全的对称加密算法，支持不同长度的密钥。它经常用于安全通信和数据保护领域。

19、非对称加密及常见的算法名称？

非对称加密算法，也称为公钥加密算法，是一种加密技术，使用一对密钥：一个公钥和一个私钥。这两个密钥用于加密和解密数据，其中一个用于加密，另一个用于解密。

1. RSA：一种非对称加密算法，以其数学基础和安全性而闻名。它使用一个公钥和一个私钥，通常用于数字签名、密钥交换和数据加密。
2. DSA：一种用于数字签名的非对称加密算法，通常与其他加密算法一起使用来确保数据的完整性和认证性。
3. ECC：一种基于椭圆曲线数学的非对称加密算法。它提供了与传统非对称算法相比更短的密钥长度，同时保持相同的安全性。
4. DH：一种密钥交换协议，而不是用于数据加密的具体算法。它允许两个通信方在不共享密钥的情况下协商共享的加密密钥。
5. ElGamal：一种基于离散对数问题的非对称加密算法，通常用于密钥交换和数字签名。

20、算法：多叉树的层次遍历 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

思路：

1. 创建一个队列，开始时将根节点入队。
2. 进入循环，直到队列为空。在每个循环迭代中，处理队列中当前层的节点。
3. 计算当前队列的大小，这个大小表示当前层的节点数。
4. 遍历处理队列中的这些节点：出队一个节点，将其值存储到结果中，并将其所有子节点入队。
5. 重复步骤 2 直到队列为空，此时你就得到了层序遍历的结果。

示例代码：

#include <iostream>
#include <vector>
#include <queue>

// N 叉树节点的定义
class Node {
public:
    int val;
    std::vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, std::vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

std::vector<std::vector<int>> levelOrder(Node* root) {
    std::vector<std::vector<int>> result;
    if (root == nullptr) {
        return result;
    }

    std::queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size(); // 当前层的节点数量
        std::vector<int> levelNodes;

        for (int i = 0; i < levelSize; i++) {
            Node* node = q.front();
            q.pop();

            levelNodes.push_back(node->val);

            for (Node* child : node->children) {
                if (child != nullptr) {
                    q.push(child);
                }
            }
        }

        result.push_back(levelNodes);
    }

    return result;
}

int main() {
    // 创建一个 N 叉树，以示例为例
    Node* root = new Node(1);
    Node* child1 = new Node(3);
    Node* child2 = new Node(2);
    Node* child3 = new Node(4);
    root->children = {child1, child2, child3};
    child1->children = {new Node(5), new Node(6)};

    std::vector<std::vector<int>> result = levelOrder(root);

    // 输出层序遍历结果
    for (const auto& level : result) {
        for (int val : level) {
            std::cout << val << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}