阿Q技术站

深浅色

快手C++一面 ​

1、虚函数实现原理 ​

虚函数的实现依赖于虚函数表（Virtual Table，简称 vtable） 和 虚函数指针（Virtual Pointer，简称 vptr）。

  1. 虚函数表（vtable）： 编译器为每个包含虚函数或继承自包含虚函数的类的类型生成一个静态的、只读的虚函数表。vtable 存储了该类所有虚函数的地址。如果派生类重写（Override）了基类的虚函数，vtable 中对应位置存储的就是派生类函数的地址；否则，存储的是基类函数的地址。
  2. 虚函数指针（vptr）： 编译器会在含有虚函数的类的对象中添加一个隐藏的成员变量，即虚函数指针 vptr。vptr 位于对象内存布局的起始位置（或特定位置，取决于编译器），它指向该对象所属类的 vtable。

运行时机制： 当通过基类指针或引用调用虚函数时（即多态调用），程序会执行以下步骤：

  1. 通过基类指针/引用访问对象的内存。
  2. 读取对象起始位置的 vptr，获取到该对象实际类型的 vtable 地址。
  3. 根据被调用虚函数在 vtable 中的固定索引（这个索引在编译时确定），查找对应的函数地址。
  4. 通过该地址调用正确的函数实现，从而实现运行时多态。

2、虚表是一个类有一个还是一个对象有一个？ ​

虚函数表（vtable）是一个类有一个，而虚函数指针（vptr）是一个对象有一个。

  • vtable (类级别)： vtable 是类的静态属性，存储在程序的只读数据段（.rodata 或类似区域）。同一个类的所有对象共享同一个 vtable。
  • vptr (对象级别)： vptr 是对象的一个隐藏成员变量，它在对象实例化时被初始化，并指向其所属类的 vtable。因此，每个多态类的对象都会多占用一个指针大小的内存空间来存储 vptr。

3、查询虚表的时间复杂度是多少？ ​

O(1)

虚函数调用过程本质上是两次解引用（或一次解引用加一次索引查找）：

  1. 通过对象指针/引用找到 vptr。
  2. 通过 vptr 找到 vtable。
  3. 通过编译期确定的固定索引（Offset）在 vtable 中找到目标函数地址。

由于虚函数在 vtable 中的位置（索引）在编译时就已经确定，因此查找过程不涉及任何搜索或遍历，是一个直接的地址查找和跳转操作，效率非常高。

4、 std::move() 原理，涉及移动吗？ ​

std::move() 本身不进行任何移动操作，它仅仅是一个类型转换函数。

std::move(T&& obj) 的作用是将一个左值（Lvalue）强制转换为对应的右值引用。

  1. 左值到右值引用： 它通过 static_cast<typename std::remove_reference<T>::type&&>(t) 实现。
  2. 触发移动： 真正的“移动”操作是在转换后的右值引用作为参数，去匹配目标类的移动构造函数 或 移动赋值运算符 时发生的。

std::move() 是移动语义的前提，它告诉编译器：“这个对象我不再需要了，你可以安全地从它那里窃取资源（Steal Resources）。” 实际的资源转移（移动）是由目标类的移动构造函数/赋值运算符完成的。

5、假设有一个 1KB 的大对象，move 能节省拷贝吗？ ​

能，但取决于该对象是否实现了移动语义。

  1. 如果对象实现了移动语义（例如 std::vector, std::string）：

    • 节省拷贝： move 将极大地节省时间。对于一个 1KB 的对象，如果它内部包含指向堆内存的指针（例如 std::vector），移动操作只需要拷贝指针、长度等少量元数据（通常是 8 到 24 字节），然后将源对象的指针置空。这避免了对 1KB 实际数据的深度拷贝。
    • 时间复杂度： 移动操作的时间复杂度通常为 O(1)。

  2. 如果对象未实现移动语义（例如一个普通的 1KB 结构体）：

    • 不节省拷贝： 此时，编译器会退而求其次，调用该对象的拷贝构造函数。
    • 时间复杂度： 拷贝操作的时间复杂度为 O(N)，其中 N 是对象的大小，即需要拷贝 1KB 的数据。

对于包含堆资源的“大对象”而言，std::move 只有在配合目标对象的移动构造函数/赋值运算符时，才能发挥其性能优势，将 O(N) 的深拷贝优化为 O(1) 的浅拷贝加指针转移。

6、智能指针原理 ​

详细的可以看之前总结的：点击阅读

智能指针核心原理适用场景关键特性
std::unique_ptr独占所有权。通过禁用拷贝构造函数和拷贝赋值运算符，确保任何时候只有一个 unique_ptr 指向管理的对象。支持通过 std::move 转移所有权。独占资源、函数返回值、Pimpl 模式。轻量级，性能接近裸指针，支持自定义删除器。
std::shared_ptr共享所有权。通过引用计数（Reference Count） 机制实现。多个对象需要共享同一资源时。内部维护一个控制块（Control Block），包含引用计数和弱引用计数。当引用计数降为零时，释放资源。
std::weak_ptr非所有权观察者。它指向 shared_ptr 管理的对象，但不增加引用计数。解决 shared_shared 之间的循环引用问题。必须通过 lock() 方法转换为 shared_ptr 才能访问资源，如果资源已被释放，lock() 返回空的 shared_ptr。

7、new 和 malloc 有什么区别呢？ ​

详细区别：点击阅读

特性new 运算符 / new[]malloc() 函数
语言C++ 运算符（Operator）C 标准库函数
内存分配既分配内存，又调用构造函数初始化对象。仅分配原始内存块，不进行对象初始化。
内存释放对应 delete / delete[]，会先调用析构函数，再释放内存。对应 free()，仅释放内存块。
类型安全返回指定类型的指针，是类型安全的，无需显式类型转换（Cast）。返回 void*，需要显式类型转换为目标类型，非类型安全。
错误处理分配失败时，默认抛出 std::bad_alloc 异常。分配失败时，返回 NULL 指针。
重载可以被用户重载（作为成员函数或全局函数）。不能被用户重载。
数组使用 new[] 分配数组，delete[] 释放，delete[] 会正确调用每个元素的析构函数。分配数组，但不知道元素个数，释放时不会调用析构函数。

8、用 new 生成的对象，可以用 free 释放吗？那如果是基础类型呢？ ​

通常情况下，不行。

  1. 对于类对象： 绝对不能用 free 释放用 new 分配的类对象。new 运算符执行了两个步骤：分配内存（通过 operator new）和调用构造函数。delete 运算符也执行两个步骤：调用析构函数和释放内存（通过 operator delete）。如果使用 free 释放，则对象的析构函数不会被调用，可能导致资源泄漏（如文件句柄、网络连接等）。
  2. 对于基础类型（如 int, float）： 理论上，基础类型没有构造函数和析构函数，new int 内部调用的是全局的 operator new，而 malloc 最终也是调用操作系统底层的内存分配函数。如果 new 和 malloc 最终使用的是同一套内存分配机制（例如 glibc 的 ptmalloc），那么技术上可能可以混用。但是，C++ 标准明确规定：new 分配的内存必须用 delete 释放，malloc 分配的内存必须用 free 释放。混用是未定义行为（Undefined Behavior），在实际工程中是严格禁止的，因为它依赖于编译器和运行库的具体实现。

9、用 new 创建数组时，释放的时候需要写出元素个数吗？ ​

不需要，但必须使用 delete[]。

当你使用 new[] 创建数组时，例如 int *p = new int[10];，编译器会在分配的内存块中额外存储数组的元素个数（或一个用于计算元素个数的元数据）。

当你调用 delete[] p; 时：

  1. 程序会从 p 指向的地址前读取这个隐藏的元数据，得知数组的元素个数。
  2. 然后，如果数组元素是类类型，它会从后往前依次调用每个元素的析构函数。
  3. 最后，它会释放整个内存块。

如果你错误地使用了 delete p; 而不是 delete[] p;：

  • 如果元素是基础类型（如 int），可能不会立即崩溃，但行为是未定义的，且可能导致内存泄漏。
  • 如果元素是类类型，则只会调用第一个元素的析构函数，并可能导致内存损坏或程序崩溃。

释放数组时，使用 delete[] 是告诉运行时系统“这是一个数组，需要按数组方式释放”。元素个数信息由系统内部维护。

10、std::map 和 B+ tree 有什么区别呢？ ​

特性std::mapB+ Tree
数据结构红黑树（Red-Black Tree），一种自平衡二叉搜索树（BST）。一种多路平衡查找树。
存储位置主要用于内存（RAM）中的数据存储。主要用于磁盘（Disk）或 SSD 等外部存储的索引结构。
节点大小节点通常只包含一个键值对和两个指针。节点大小较小。节点（页/块）大小通常与磁盘页大小对齐（如 4KB 或 16KB），包含多个键值对和指针。
查找效率O(log N)，N 是元素总数。查找效率高，但在磁盘 I/O 上效率低。O(log_b N)，b 是分支因子（节点能容纳的键值对数量）。树高矮，磁盘 I/O 次数少。
数据存储键值对存储在树的所有节点中。所有数据（键值对）只存储在叶子节点中，非叶子节点只存储键和指针，用于索引。
范围查询较复杂，需要中序遍历。非常高效。叶子节点之间通过指针连接成一个有序链表，范围查询只需定位到起始点，然后沿链表顺序遍历即可。

std::map 针对内存访问优化，平衡了查找、插入和删除的效率。B+ Tree 针对磁盘 I/O 优化，通过减少树高和利用叶子节点的顺序链表，极大地提升了范围查询的性能。

11、红黑树和 B+ Tree 在性能、内存空间占用上的对比？ ​

特性红黑树（Red-Black Tree）B+ Tree
查找性能O(log N)。在内存中表现优秀，但由于树高较高，在磁盘 I/O 场景下性能较差。O(log_b N)。树高极矮（通常 3-4 层），查找所需的磁盘 I/O 次数极少，性能极佳。
插入/删除性能O(log N)。操作相对简单，需要进行颜色调整和旋转。O(log_b N)。操作可能涉及页分裂、合并和平衡，相对复杂，但 I/O 次数少。
范围查询性能O(log N + K) (K 为范围内的元素数)。需要多次回溯和遍历，效率一般。O(log_b N + K)。定位起始点后，只需在叶子节点链表上顺序遍历，效率极高。
内存空间占用较高。每个节点只存储一个数据，但需要额外的颜色位和指针。节点利用率低。较低且高效。节点（页）被设计为与磁盘块大小一致，内部填充了大量键值对，空间利用率高。非叶子节点不存储数据，进一步节省空间。
适用场景内存数据库、std::map、调度器等对单次查找和平衡要求高的场景。磁盘数据库索引（MySQL InnoDB/MyISAM）、文件系统等需要最小化磁盘 I/O 的场景。

12、为什么数据库选择 B+ Tree 而不是红黑树？ ​

数据库（如 MySQL 的 InnoDB 存储引擎）选择 B+ Tree 作为索引结构的主要原因在于其对磁盘 I/O的优化和对范围查询的天然支持。

  1. 减少磁盘 I/O 次数（核心原因）：

    • 磁盘 I/O 是数据库操作中最慢的瓶颈。
    • B+ Tree 的节点设计得很大（通常 4KB 或 16KB），可以容纳数百个索引项，这使得树的高度极低（通常只有 3-4 层）。
    • 树的每一层节点对应一次磁盘 I/O。极低的树高意味着从根节点到叶子节点查找一个数据，只需要 3 到 4 次磁盘 I/O。
    • 红黑树是二叉树，树高较高，每个节点只存储一个数据，查找相同数量的数据可能需要数十次甚至上百次 I/O，效率低下。

  2. 高效的范围查询：

    • B+ Tree 的所有数据都存储在叶子节点，并且叶子节点之间通过指针连接成一个有序链表。
    • 进行范围查询时，只需在非叶子节点中定位到范围的起始叶子节点，然后沿着叶子节点的链表进行顺序遍历即可，这避免了大量的随机 I/O，效率极高。
    • 红黑树进行范围查询需要中序遍历，涉及大量的节点跳转，不利于磁盘预读和顺序访问。

B+ Tree 的设计哲学是**“多路查找”**，用更宽的节点（牺牲内存空间换取 I/O 次数）来最小化磁盘 I/O，这完美契合了数据库索引的性能需求。

13、在STL里，内存池是怎么实现的，有怎样的结构？ ​

在 C++ STL 中，内存池（Memory Pool）主要体现在 std::allocator 的早期实现（如 SGI STL 的 std::allocator）中，以及某些容器（如 std::list, std::map）的默认分配器中，目的是为了减少频繁的小对象内存分配和释放带来的开销和内存碎片。

SGI STL 内存池（std::allocator 的经典实现） ​

SGI STL 的分配器（std::alloc）通常采用两级分配器：

  1. 一级分配器： 当请求的内存大于 128 字节时，直接使用 malloc 和 free 进行分配和释放。
  2. 二级分配器（内存池核心）： 当请求的内存小于等于 128 字节时，使用内存池机制。

二级分配器的结构：

  • 自由链表（Free Lists）： 维护 16 个自由链表，分别管理 8 字节的倍数大小的内存块（8, 16, 24, ..., 128 字节）。每个链表节点是一个指向下一个空闲块的指针。
  • 内存块分配： 当用户请求N 字节内存时，分配器会向上取整到M（8 的倍数），然后去第M/8 - 1 个自由链表中查找是否有空闲块。
    • 命中： 如果链表非空，直接返回链表的第一个节点，O(1) 完成分配。
    • 未命中： 如果链表为空，则向大内存池（Heap）请求一块更大的内存（通常是 20 个块的大小），将这 20 个块连接到对应的自由链表上，然后返回一个块给用户。

极大地提高了小对象的分配速度（O(1)），并有效减少了内存碎片。

现代 C++ 标准库的 std::allocator 通常不再包含这种复杂的内存池实现，而是直接封装 ::operator new 和 ::operator delete，将内存管理交由操作系统和运行时库的优化。但 std::pmr::polymorphic_allocator 提供了更灵活的内存池定制能力。

14、执行 vector<int> v(4, 100) 会发生什么，在栈上还是堆上分配？ ​

会发生以下情况：

  1. 栈上分配（对象本身）： v 这个 std::vector 对象本身（包含三个成员：指向数据的指针、容量、大小）是在栈上分配的。
  2. 堆上分配（实际数据）： vector 的实际元素数据（4 个 int，值为 100）是在堆上分配的。
    • vector 的构造函数会调用内存分配器（通常是 new）在堆上分配足够的内存来存储 4 个 int。
    • 然后，它会调用 int 的构造函数（对于基础类型是值初始化）将这 4 个位置都设置为 100。

v 变量本身在栈上，但它管理的 4 个 int 元素在堆上。当 v 超出作用域时，栈上的 v 对象被销毁，其析构函数会自动释放堆上的 4 个 int 占用的内存。

15、那如果是 new vector<int>(4,100) 呢？ ​

new vector<int>(4, 100) 会发生以下情况：

  1. 堆上分配（对象本身）： std::vector 对象本身（包含 vptr、指针、容量、大小等成员）是在堆上分配的。new 操作符会返回一个指向这个堆上 vector 对象的指针。
  2. 堆上分配（实际数据）： vector 构造函数内部，其实际元素数据（4 个 int，值为 100）也会在堆上分配。

这种情况下，涉及两次堆内存分配：一次是为 vector 对象本身分配，一次是为 vector 内部的元素数据分配。

释放： 必须使用 delete 释放 vector 对象本身，delete 会调用 vector 的析构函数，而析构函数又会自动释放内部元素数据占用的堆内存。

cpp
// 第一次堆分配: new vector<int>(4, 100)
// 第二次堆分配: vector 内部为 4 个 int 分配空间
std::vector<int>* p_v = new std::vector<int>(4, 100);

// 释放内部数据和 vector 对象本身
delete p_v;

16、如何拿到类中私有成员变量的值？ ​

在 C++ 中，私有（private）成员变量是为了封装和信息隐藏而设计的，直接访问是受限的。

16.1、公开接口（推荐） ​

最正规和推荐的方式是提供公有（public）的访问器（Accessor）方法，即 Getter：

cpp
class MyClass {
private:
    int private_data = 10;
public:
    int getPrivateData() const {
        return private_data;
    }
};

16.2、友元（Friend）机制 ​

将一个函数或另一个类声明为当前类的友元，友元可以访问类的所有私有和保护成员。

cpp
class MyClass;
void printPrivateData(const MyClass& obj); // 友元函数声明

class MyClass {
private:
    int private_data = 20;
    friend void printPrivateData(const MyClass& obj); // 声明友元
};

void printPrivateData(const MyClass& obj) {
    // 友元函数可以直接访问私有成员
    std::cout << obj.private_data << std::endl;
}

16.3、运行时/调试技巧 ​

  1. 指针偏移：

    利用 C++ 对象的内存布局是确定的这一特性，通过计算私有成员相对于对象起始地址的偏移量来访问。这需要了解编译器对齐和成员变量的顺序，高度依赖编译器和平台，且在有虚函数时更复杂。

  2. 宏和强制类型转换：

    在某些旧代码或特殊场景中，可能会使用宏或 reinterpret_cast 强行将对象指针转换为一个结构体指针，该结构体具有与私有成员相同的内存布局。

    c++
    // 危险且不推荐：依赖于内存布局
#define ACCESS_PRIVATE_MEMBER(object, member) \
    (*reinterpret_cast<decltype(&(object.member))>( \
        reinterpret_cast<char*>(&(object)) + \
        offsetof(std::remove_reference<decltype(object)>::type, member)))

  3. 调试器/反射库：

    在调试时，调试器（如 GDB, Visual Studio Debugger）可以访问任何内存地址。对于需要运行时反射的场景，可以使用像 Qt 或 Boost.Hana 这样的库提供的反射机制（如果可用）。

17、有一个二维数组里面都有值，想要给每个数都加 100，行遍历和列遍历有什么区别？ ​

假设二维数组 A[R][C] 存储在内存中，C++ 默认采用行主序（Row-Major Order） 存储，即同一行的元素在内存中是连续存放的。

遍历方式内存访问模式性能影响总结
行遍历for (i) { for (j) { A[i][j] += 100; } }连续访问。访问 A[i][j] 后紧接着访问 A[i][j+1]，这与内存的物理存储顺序一致。性能更优。充分利用了 CPU 的缓存局部性（Cache Locality） 原理。当访问 A[i][j] 时，整个缓存行（Cache Line）会被加载到 CPU 缓存，A[i][j+1], A[i][j+2]... 等相邻元素可以直接从缓存中读取，极大地减少了对主内存的访问。
列遍历for (j) { for (i) { A[i][j] += 100; } }跳跃访问。访问 A[i][j] 后紧接着访问 A[i+1][j]。在内存中，A[i][j] 和 A[i+1][j] 之间间隔了整个一行的长度（C 个元素）。性能较差。每次访问都可能导致缓存未命中（Cache Miss），因为下一个元素不在当前的缓存行中。这会导致 CPU 频繁地从较慢的主内存中加载数据，性能显著低于行遍历。

在 C++（以及 C、Java、Python 等采用行主序的语言）中，对二维数组进行操作时，行遍历的性能远优于列遍历。

18、在浏览器中访问一个 http 服务器，这里面会经过哪些协议？ ​

用户输入 URL 到最终看到网页内容，涉及一个复杂的协议栈交互过程。

主要协议包括：

协议层协议名称作用
应用层HTTP/HTTPS客户端（浏览器）与服务器之间的通信协议，定义了数据如何封装和传输（请求/响应）。
DNS (Domain Name System)将域名（如 www.example.com）解析为 IP 地址。这是建立连接的第一步。
传输层TCP (Transmission Control Protocol)提供可靠的、面向连接的、基于字节流的数据传输服务。HTTP 默认基于 TCP。
UDP (User Datagram Protocol)提供不可靠的、无连接的数据传输服务。DNS 查询通常使用 UDP。
网络层IP (Internet Protocol)负责数据包（Datagram）在网络中的路由和寻址，确保数据包从源地址到达目的地址。
ICMP (Internet Control Message Protocol)用于网络诊断和错误报告（如 Ping）。
数据链路层ARP (Address Resolution Protocol)将 IP 地址解析为 MAC 地址，用于在局域网内进行数据帧的传输。
Ethernet / Wi-Fi负责在物理介质上传输数据帧。
物理层各种物理介质和信号标准。负责比特流的传输。

简要流程：

  1. DNS 解析： 浏览器调用 DNS 协议获取服务器 IP。
  2. TCP 连接： 浏览器与服务器进行 TCP 三次握手，建立可靠连接。
  3. HTTP 请求： 浏览器通过 HTTP 协议发送请求报文。
  4. 服务器处理与响应： 服务器处理请求，并通过 TCP 发送 HTTP 响应报文。
  5. 数据传输： TCP 将 HTTP 报文切分成段，IP 将段封装成包，通过底层协议传输。
  6. TCP 断开： 传输完成后，进行 TCP 四次挥手，断开连接。
  7. 渲染： 浏览器接收到数据，解析 HTML、CSS、JavaScript 并渲染页面。

19、为什么不直接用 tcp 协议，还需要用 http 协议？ ​

这是一个关于协议分层和职责分离的核心问题。

TCP 协议（传输层）和 HTTP 协议（应用层）处于不同的协议层，它们解决的问题和承担的职责是完全不同的。

协议协议层核心职责为什么不能替代 HTTP？
TCP传输层可靠的、有序的、流量控制的数据传输。它关注的是“如何把数据从一端可靠地传输到另一端”。TCP 只提供字节流服务，它不知道这些字节流代表什么业务含义（是网页、邮件还是文件）。它缺乏应用层的语义和结构。
HTTP应用层定义客户端和服务器之间的通信格式和语义。它关注的是“这些数据代表什么资源，以及如何操作这些资源”。HTTP 定义了：请求方法（GET, POST, PUT, DELETE）、资源定位（URL/URI）、状态码（200, 404, 500）、头部字段（Header）等，这些都是应用层交互所必需的结构和语义。
  • HTTP 需要 TCP 提供的可靠传输服务： HTTP 依赖 TCP 来确保请求和响应数据包不会丢失、不会乱序。
  • TCP 不能替代 HTTP 提供的应用语义： 如果直接使用 TCP，程序员需要自己定义一套规则来区分请求类型、资源路径、数据格式、错误处理等，这本质上就是在重新发明一个私有的 HTTP 协议。

每一层只关注自己的职责，上层协议可以复用下层协议提供的服务。HTTP 专注于应用逻辑，而将复杂的网络传输细节交给 TCP/IP 栈处理，实现了高效的模块化设计。

20、1,2,3,4,...,n 构造二叉搜索树。 ​

20.1、问题描述 ​

给定一个整数n，要求生成所有由1到n 构成的、结构上唯一的二叉搜索树（Binary Search Tree, BST）。

示例：

输入：n = 3 输出: 5 棵 BST

由1, 2, 3 构成的 5 棵唯一的 BST 结构如下：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

20.2、解题思路：递归与动态规划 ​

核心思想：分治 ​

二叉搜索树（BST）的特性是：

  1. 节点的值大于其左子树中所有节点的值。
  2. 节点的值小于其右子树中所有节点的值。

对于给定的有序序列1, 2,..., n，可以选择序列中的任意一个数字i作为根节点。一旦确定了根节点i，整个问题就被分解为两个独立的子问题：

  1. 左子树：由小于i 的数字（即1, 2, ..., i-1）构成。
  2. 右子树：由大于i 的数字（即i+1, i+2, ..., n）构成。

由于左右子树的构造是独立的，只需要递归地求出所有可能的左子树集合L 和所有可能的右子树集合R，然后将i 作为根节点，将L 中的每棵树与R 中的每棵树进行组合，即可得到以i 为根的所有 BST。

递归函数的定义 ​

定义一个递归函数 generateTrees(start, end)，它返回一个列表，列表中包含所有由序列 start 到 end 构成的 BST 的根节点。

递归步骤：

  1. 基本情况：

    如果 start > end，表示序列为空，即空树。此时应返回一个包含一个 nullptr（空指针）的列表，表示这是一个有效的空子树。

  2. 递归构建：

    • 遍历 i 从 start 到 end，将每个 i 作为当前的根节点。

    • 递归调用 generateTrees(start, i - 1) 得到所有可能的左子树集合L。

    • 递归调用 generateTrees(i + 1, end) 得到所有可能的右子树集合R。

    • 组合： 遍历L 中的每棵左子树l 和R 中的每棵右子树r：

      创建一个新的根节点i。

      将l设置为根节点的左孩子，将r设置为根节点的右孩子。

      将新构造的树加入到结果列表中。

20.3、参考代码 ​

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory>

// 定义二叉搜索树的节点结构
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    // 构造函数
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

/**
 * @brief 递归函数：生成从 start 到 end 范围内所有可能的二叉搜索树
 * 
 * @param start 范围起始值
 * @param end 范围结束值
 * @return std::vector<TreeNode*> 包含所有唯一BST根节点的向量
 */
std::vector<TreeNode*> generateTreesRecursive(int start, int end) {
    std::vector<TreeNode*> all_trees;

    // 1. 基础情况：如果起始值大于结束值，表示空区间，返回包含一个空指针的向量
    if (start > end) {
        all_trees.push_back(nullptr);
        return all_trees;
    }

    // 2. 递归构建
    for (int i = start; i <= end; ++i) {
        // i 作为当前子树的根节点
        
        // 2.1 递归构建左子树 (start 到 i-1)
        std::vector<TreeNode*> left_trees = generateTreesRecursive(start, i - 1);
        
        // 2.2 递归构建右子树 (i + 1 到 end)
        std::vector<TreeNode*> right_trees = generateTreesRecursive(i + 1, end);

        // 2.3 组合左右子树
        // 遍历所有可能的左子树和右子树的组合
        for (TreeNode* l_root : left_trees) {
            for (TreeNode* r_root : right_trees) {
                // 创建当前根节点
                // 注意：这里是创建新的根节点，但左右子树的指针是共享的（因为它们是递归返回的结果）
                // 这种共享是安全的，因为只是在构建不同的父节点来指向它们。
                TreeNode* root = new TreeNode(i);
                
                // 链接左右子树
                root->left = l_root;
                root->right = r_root;
                
                all_trees.push_back(root);
            }
        }
    }
    
    return all_trees;
}

// 生成所有唯一二叉搜索树
std::vector<TreeNode*> generateTrees(int n) {
    if (n == 0) {
        return {};
    }
    return generateTreesRecursive(1, n);
}

// 打印树结构（前序遍历，方便查看）
void printTree(TreeNode* root) {
    if (!root) {
        std::cout << "null";
        return;
    }
    std::cout << root->val;
    if (root->left || root->right) {
        std::cout << "(";
        printTree(root->left);
        std::cout << ",";
        printTree(root->right);
        std::cout << ")";
    }
}

// 释放所有树的内存
// 重要：由于使用了原始指针，必须手动清理内存以避免内存泄漏。
void deleteTrees(const std::vector<TreeNode*>& trees) {
    for (TreeNode* root : trees) {
        // 使用栈进行非递归后序遍历释放内存
        if (!root) continue;
        
        // 采用后序遍历（左右根）来安全删除
        std::vector<TreeNode*> stack;
        std::vector<TreeNode*> output; // 存储后序遍历的结果
        TreeNode* current = root;
        TreeNode* last_visited = nullptr;

        while (current || !stack.empty()) {
            if (current) {
                stack.push_back(current);
                current = current->left;
            } else {
                TreeNode* peek = stack.back();
                // 如果右子树不存在，或者右子树已经被访问过
                if (peek->right == nullptr || peek->right == last_visited) {
                    output.push_back(peek);
                    stack.pop_back();
                    last_visited = peek;
                } else {
                    current = peek->right;
                }
            }
        }
        
        // 遍历 output 列表进行删除
        for (TreeNode* node : output) {
            delete node;
        }
    }
}

int main() {
    int n = 3; // 示例：n=3
    std::cout << "生成 n=" << n << " 的所有唯一二叉搜索树...\n";
    
    std::vector<TreeNode*> result = generateTrees(n);
    
    std::cout << "总共找到 " << result.size() << " 棵唯一的BST。\n";
    std::cout << "以 (根(左子树,右子树)) 的形式打印所有树的结构：\n";

    for (size_t i = 0; i < result.size(); ++i) {
        std::cout << "Tree " << i + 1 << ": ";
        printTree(result[i]);
        std::cout << "\n";
    }
    
    // 内存清理
    deleteTrees(result);
    
    return 0;
}

运行结果：

运行结果

21、合并两个有序数组 a 和 b。 ​

21.1、问题描述与分析 ​

给定两个已排序的数组 A 和 B，要求将它们合并成一个新的有序数组 C。

这个问题是归并排序算法中的核心步骤，是处理有序数据的基础操作。由于输入数组 A 和 B 已经有序，可以利用这一特性，避免进行完整的排序操作，从而达到最优的时间复杂度。

最优解法目标：

  • 时间复杂度： 达到 O(m + n)，其中 m 和 n 分别是数组 A 和 B 的长度。
  • 空间复杂度： O(m + n)（如果允许创建新数组）或 O(1)（如果要求原地合并，但原地合并通常要求一个数组有足够的空间容纳另一个数组）。

21.2、解题思路：双指针法 ​

双指针法是解决此类有序数组问题的最有效手段。

核心思想 ​

分别用两个指针 p_A 和 p_B 指向数组 A 和 B 的起始位置（即索引 0）。在每一步操作中，比较 A[p_A] 和 B[p_B] 的值，将较小的那个元素放入结果数组 C 中，并将对应的指针向前移动一步。

步骤详解 ​

  1. 初始化：

    • 创建结果数组 C，预留m + n的空间。
    • 初始化指针p_A = 0，p_B = 0。

  2. 主循环：

    当p_A < m且p_B < n时，执行循环：

    • 如果A[p_A] < B[p_B]，将A[p_A]加入 C，并递增 p_A。
    • 否则（B[p_B] < A[p_A]），将B[p_B]加入 C，并递增 p_B。

  3. 收尾工作：

    • 主循环结束后，说明其中一个数组的所有元素都已处理完毕，另一个数组中可能还有剩余元素。
    • 将数组 A 中剩余的元素（从 p_A 开始）依次加入 C。
    • 将数组 B 中剩余的元素（从 p_B 开始）依次加入 C。
复杂度分析 ​
  • 时间复杂度： O(m + n)。因为每个元素只会被比较和添加到结果数组中一次。
  • 空间复杂度： O(m + n)。这是因为创建了一个新的数组 C 来存储结果。

21.3、C++ 参考代码（合并到新数组） ​

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

/**
 * @brief 合并两个有序数组 A 和 B 到一个新的数组 C 中。
 * 
 * @param A 有序数组 A
 * @param B 有序数组 B
 * @return std::vector<int> 合并后的有序数组 C
 */
std::vector<int> merge_to_new_array(const std::vector<int>& A, const std::vector<int>& B) {
    int m = A.size();
    int n = B.size();
    std::vector<int> C;
    C.reserve(m + n); // 预分配空间，提高效率

    int pA = 0; // 指向数组 A 的指针
    int pB = 0; // 指向数组 B 的指针

    // 1. 核心合并过程：当两个指针都没有越界时
    while (pA < m && pB < n) {
        if (A[pA] <= B[pB]) {
            C.push_back(A[pA]);
            pA++;
        } else {
            C.push_back(B[pB]);
            pB++;
        }
    }

    // 2. 将数组 A 中剩余的元素添加到 C
    while (pA < m) {
        C.push_back(A[pA]);
        pA++;
    }

    // 3. 将数组 B 中剩余的元素添加到 C
    while (pB < n) {
        C.push_back(B[pB]);
        pB++;
    }

    return C;
}

// 打印数组内容
void print_array(const std::vector<int>& arr) {
    std::cout << "[";
    for (size_t i = 0; i < arr.size(); ++i) {
        std::cout << arr[i];
        if (i < arr.size() - 1) {
            std::cout << ", ";
        }
    }
    std::cout << "]";
}

int main() {
    // --- 测试用例 1: 正常合并 ---
    std::vector<int> A1 = {1, 3, 5, 7};
    std::vector<int> B1 = {2, 4, 6, 8, 10};
    std::cout << "--- 测试用例 1: 正常合并 ---\n";
    std::cout << "数组 A: "; print_array(A1); std::cout << "\n";
    std::cout << "数组 B: "; print_array(B1); std::cout << "\n";

    std::vector<int> C1 = merge_to_new_array(A1, B1);
    std::cout << "合并结果 C: "; print_array(C1); std::cout << "\n\n";

    // --- 测试用例 2: 一个数组为空 ---
    std::vector<int> A2 = {10, 20, 30};
    std::vector<int> B2 = {};
    std::cout << "--- 测试用例 2: 一个数组为空 ---\n";
    std::cout << "数组 A: "; print_array(A2); std::cout << "\n";
    std::cout << "数组 B: "; print_array(B2); std::cout << "\n";

    std::vector<int> C2 = merge_to_new_array(A2, B2);
    std::cout << "合并结果 C: "; print_array(C2); std::cout << "\n\n";

    // --- 测试用例 3: 元素完全交错 ---
    std::vector<int> A3 = {1, 10, 20};
    std::vector<int> B3 = {5, 15, 25};
    std::cout << "--- 测试用例 3: 元素完全交错 ---\n";
    std::cout << "数组 A: "; print_array(A3); std::cout << "\n";
    std::cout << "数组 B: "; print_array(B3); std::cout << "\n";

    std::vector<int> C3 = merge_to_new_array(A3, B3);
    std::cout << "合并结果 C: "; print_array(C3); std::cout << "\n\n";

    return 0;
}

运行结果：

运行结果