TodoList

[ ] leetcode.654 最大二叉树通过单调栈进行优化，时间复杂度：$O(n^2) -> O(n)$
[ ] 树的O(1)空间复杂度处理： Morris 遍历

编码问题记录

1.你的代码问题在于:每次拼接字符串时都创建了新对象:

1	new_str = new_str + c; // ← 每次都创建新字符串,效率极低!

这会导致大量的内存分配和拷贝操作。应该使用 push_back() 或 += 操作符:

💡 额外的小建议：拼接字符串的方式

你在收集结果时：

string new_string = "";
for(auto & v :path){
    new_string += v;
}

这种写法也是可以的，但更优雅的 C++ 写法是直接利用 string 的构造函数：

1	1res.emplace_back(path.begin(), path.end());

这样不仅代码更简洁，而且 emplace_back 是原地构造，避免了额外的字符串拷贝，性能更好。

2.简化 pair 构造语法

// ❌ 冗长写法
q.push(pair<TreeNode *,int>(root,0));
q.push(pair<TreeNode *,int>(curr.first->left,curr.second + 1));

// ✅ 使用 make_pair 或直接初始化
q.push({root, 0});
q.push({curr.first->left, curr.second + 1});

3.用位运算替代 $2^n$

节点数 = $2^h - 1 $

用位运算表示 $(1 << h) - 1$ 注意，这里的括号不可以省略，因为<<运算符的优先级没有 - 运算符高

要养成2的n次方使用位运算，而不是pow(2,n);

4.动态的容器的大小不可以放在for循环中

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) 
    {   
        queue<TreeNode *> q;
        q.push(root);
        int left_num = 0;
        while(!q.empty()){
            for(int i =0;i < q.size();i++)// 注意 这里的q.size放在了for循环中
            {
                TreeNode* new_node = q.front();
                std::cout << new_node->val << " "<< i << std::endl;
                if(i==0){
                    left_num = new_node->val;
                }
                q.pop();
                if(new_node->left){
                    q.push(new_node->left);   // 但是q的大小在循环的过程中会发生改变，导致循环继续进行
                }
                if(new_node->right){
                    q.push(new_node->right);
                }
            }
        }
        return left_num;
    }
};

这是一个经典的 **BFS 层序遍历陷阱**：

问题分析

在第 26 行的 for 循环中，你使用了 i < q.size() 作为循环条件。但问题是：

q.size() 是动态变化的：在循环内部，你会不断 push 新的节点（左子节点和右子节点）到队列中
导致循环次数错误：q.size() 会随着新节点的加入而增大，导致 for 循环执行次数超过当前层的实际节点数

例如：

第 1 层有 1 个节点，但处理时会 push 2 个子节点
此时 q.size() 从 1 变成 2，循环会多执行

5. 哨兵节点 (对所有结点处理一致化)

为了处理过程的一致性，可以考虑加入哨兵节点来达成处理一致的目的

题目链接： Leetcode.450 删除二叉搜索树中的节点

TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root){
            return nullptr;
        }
        // 注意此处，如果如果遍历到头结点的情况，pre会为nullptr，无法用pre找到与需删除节点的关系，从而导致需要额外处理头结点，多了该if逻辑
        if(root->val == key){
            if(root->left && root->right){
                TreeNode* tmp = root;
                root = tmp->left;
                TreeNode* p = root;
                while(p->right){
                    p = p->right;
                }
                p->right = tmp->right;
            }
            else if(root->left && !root->right){
                root = root->left;
            }
            else if(root->right && !root->left){
                root = root->right;
            }
            else{
                root = nullptr;
            }
        }
        TreeNode* p = root;
        TreeNode* pre = nullptr; // 此处pre节点初始值为空
        while(p){ //  该逻辑在头结点为结果节点的时候，无法生效，因为pre为nullptr，与p无关系存在
            if(p->val > key)
            {
                pre = p;
                p = p->left;
            }
            else if(p->val < key){
                pre = p;
                p = p->right;
            }
            else if(pre)
            {
                //分多钟情况讨论：
                // 1：如果是叶子结点
                std::cout <<p->val <<std::endl;
                if(!p->left && !p->right){
                    pre->left == p? pre->left = nullptr : pre->right =nullptr;
                }
                else if(p->left && !p->right)
                {
                    if(pre->left == p){
                        pre ->left = p->left;
                    }
                    else{
                        pre->right = p->left;
                    }
                }
                else if(p->right && !p->left)
                {
                    if(pre->left == p){
                        pre ->left = p->right;
                    }
                    else{
                        pre->right = p->right;
                    }
                }
                else{
                    // 左右节点都有
                    if(pre->left == p){
                        pre->left = p->left;
                    }
                    else{
                        pre->right = p->left;
                    }
                    TreeNode* tmp = p->right;
                    p = p->left;
                    while(p->right){
                        p = p->right;
                    }
                    p->right = tmp;
                }
                break;
            }
        }
        return root;
    }

如上，由于头结点不存在pre节点，导致我们在处理头结点的时候，需要额外处理，书写额外的逻辑，这增加了代码量的同时，降低了代码可读性，而且编码也会变的更复杂

在编程的途中，我们应该考虑，将所有问题的处理同质化，使得我们处理每个节点都保持相同的逻辑

所以，我们可以引入一个哨兵节点dummy 使得头结点也有pre节点

关键代码

TreeNode dummy(0);
dummy.left = root;
TreeNode* pre = dummy; //让根节点挂在dummy的左孩子上
TreeNode* p = root;

由于哨兵节点的存在，使得头结点也拥有了对应的pre节点，从而使得逻辑一致化

6. LeetCode 里不需要手动delete

LeetCode 刷题的“潜规则”

如果你是在 LeetCode 上做这道题（783. 修剪二叉搜索树或类似题目），强烈建议直接删掉 deleteBSTNode 函数和所有的 delete 操作。

LeetCode 的 C++ 环境有自动的内存管理机制（或者在评测结束后统一清理）。在算法面试中，手动 delete 节点不仅容易写出悬垂指针，还会增加不必要的代码复杂度。直接让被剪掉的节点脱离树的连接（即不再被任何指针指向），由系统去回收即可：

因为，这种程序解完就结束退出了，操作系统会自动回收应用程序各种资源。

处理delete后，直接从 $0ms->7ms$ 从击败100%到击败0.55%，有感觉吗

void deleteBSTNode(TreeNode* &root) // 其实不需要手动去delete
  {
      if(!root){
          return;
      }
      deleteBSTNode(root->left);
      deleteBSTNode(root->right);
      delete root;
      root = nullptr;
  }
  TreeNode* trimBST(TreeNode* root, int low, int high) {
      if(!root){
          return nullptr;
      }
      if(root->val < low)
      {
          deleteBSTNode(root->left);
          return trimBST(root->right,low,high);
      }
      else if(root->val > high){
          deleteBSTNode(root->right);
          return trimBST(root->left,low,high);
      }
      root->left = trimBST(root->left,low,high);
      root->right = trimBST(root->right,low,high);
      return root;
  }

7.vector的删除

8. String的删除

在 C++ 中，std::string 的字符删除操作主要涉及三个核心方法：erase()、pop_back() 以及 <algorithm> 库中的 remove()。它们各自的使用场景、底层机制和性能开销有很大差异。以下是详细的总结：

8.1. `erase()`：精准外科手术（核心删除方法）

erase() 是 std::string 的原生成员函数，功能最完备，支持删除单个字符、指定位置的字符段或迭代器区间。

常用重载形式：

按位置和长度删除：s.erase(pos, len)。从下标 pos 开始删除 len 个字符。如果省略 len，则默认删除从 pos 到字符串末尾的所有字符。
按单个迭代器删除：s.erase(it)。删除迭代器 it 指向的单个字符，并返回指向下一个有效字符的迭代器。这在循环中条件删除时非常有用，可避免迭代器失效。
按迭代器区间删除：s.erase(first, last)。删除左闭右开区间 [first, last) 内的所有字符。

⚠️ 性能与底层注意：
由于 string 底层采用连续内存存储，删除非末尾位置的字符会导致其后的所有字符向前移动（内存拷贝），产生 $ O(n) $ 的时间复杂度开销。因此，不建议在大字符串或高频循环中频繁使用 erase 删除中间位置的字符。

8.2. `pop_back()`：末端快删（轻量级删除）

pop_back() 仅用于删除字符串的最后一个字符。

特点：不涉及内存移动，仅将 size() 减 1，时间复杂度为极致的 $ O(1) $。
⚠️ 安全警告：调用前必须保证字符串非空，否则对空容器调用会引发未定义行为（Undefined Behavior）。
适用场景：栈式操作、括号匹配、路径裁剪等仅需处理末尾字符的场景。

8.3. `remove()` + `erase()`：批量删除的黄金组合

remove() 不是 string 的成员函数，而是定义在 <algorithm> 头文件中的通用算法。

remove() 的本质：它是“逻辑移除”。它会将所有不等于指定值的元素前移，并返回新逻辑结尾的迭代器，但绝不改变容器大小，也不释放内存。

Erase-Remove 惯用法：为了真正物理删除字符串中所有满足条件的字符，必须将 remove() 和 erase() 组合使用：

cpp

1
2

// 删除字符串中所有的字符 'a'
s.erase(std::remove(s.begin(), s.end(), 'a'), s.end());  // 先用remove删除所有'a',并返回新逻辑结尾的迭代器，之后调用erase删除 新逻辑结尾到旧逻辑结尾中间的元素（无效的尾部）

先由 remove将有效字符整理到前端，再用 erase 截断无效的尾部。这是 STL 泛型编程中最经典的实践之一。

8.4. 总结

删除尾部字符：首选 pop_back()，极致高效（记得判空）。
删除指定位置/区间：使用 erase(pos, len) 或迭代器版本。
删除所有满足条件的字符：使用 erase-remove 惯用法，简洁且高效。
避坑警告：绝对不要在普通的 for 循环中使用下标遍历并调用 erase，这会导致索引错乱和迭代器失效。如果必须在循环中逐个删除，应使用 erase 返回的下一个迭代器，或者采用反向遍历。

9. `string_view` (C++17 引入)：零拷贝的字符串“放大镜”

痛点：
在 C++ 中，普通的 std::string 在作为函数参数传递时，即使加了 const &，底层依然可能因为 substr() 等操作产生内存分配（堆内存分配是非常耗时的操作）。

什么是 string_view？
std::string_view 本质上是一个轻量级的视图（View）。它内部只包含两个成员：一个指向字符数组的指针（const char* ptr）和一个长度（size_t len）。它不拥有字符串的内存，只是“看”着某块内存。

优势：

零拷贝（Zero-copy）：无论你对 string_view 做多少次截取（substr）、拼接，它都只是在调整指针和长度，绝对不会分配新的内存。
无缝兼容：它可以隐式地从 std::string 或 C 风格字符串（const char*）构造。

在回溯题中的应用：
在你的 IP 地址题目中，每次 s.substr(...) 都会生成一个新的 std::string 对象。如果用 string_view，截取操作是 $ O(1) $ 的。

代码对比：

// 传统方式：每次 substr 都会分配内存
string tmp_str = s.substr(start_index, i - start_index + 1); 

// C++17 方式：仅移动指针，无内存分配
string_view tmp_str = string_view(s).substr(start_index, i - start_index + 1);

注：在 LeetCode 中，由于输入通常是 std::string，且数据量不大，string_view 带来的提升可能只有几毫秒，但在处理大文本、日志解析等实际工程场景中，它是性能神器。

10. `join` 思想：告别低效的循环拼接

痛点：
C++ 标准库（直到 C++20 之前）都没有像 Python 那样好用的 ", ".join(list) 方法。我们通常这样写：

string res;
for (const auto& v : path) {
    res += v + '.'; // 每次循环都会产生临时的 string 对象，效率极低
}
res.pop_back();

优化方案一：利用下标直接拼接（针对固定长度）
对于 IP 地址这种固定 4 段的场景，完全不需要循环。直接用下标访问 path 并拼接，既避免了循环，又避免了 pop_back() 的边界处理：

1 2	// 极其简洁且高效 res.push_back(path[0] + '.' + path[1] + '.' + path[2] + '.' + path[3]);

优化方案二：ostringstream（针对动态长度）
如果 path 的长度是不固定的（比如第 131 题分割回文串），循环拼接时 res += v + '.' 会产生大量临时对象。此时可以使用 <sstream> 库中的 ostringstream：

#include <sstream>

ostringstream oss;
for (size_t i = 0; i < path.size(); ++i) {
    if (i > 0) oss << '.';  // 除了第一个，前面加点
    oss << path[i];         // 流式插入，无临时对象
}
res.push_back(oss.str());   // 最终一次性生成 string

优化方案三：C++20 终极方案（了解即可）
如果你使用的是 C++20 标准，标准库终于补齐了这块短板，可以直接使用 std::ranges::join_view 或者 std::format：

1
2
3

// C++20 的优雅写法（目前 LeetCode 环境可能还不支持）
std::string result = path | std::views::join('.') | std::ranges::to<std::string>();

11. std::format (C++20)：类型安全的格式化神器

std::format 是 C++20 引入的类型安全、高性能格式化库，语法借鉴了 Python 的 str.format()，但在编译期就会检查参数类型和个数，彻底告别了 C 语言 printf 的崩溃风险。

基础用法：

#include <format>
#include <string>
// 自动按顺序填充占位符 {}
std::string s = std::format("Hello {}, you have {} messages", "Alice", 42);
// 结果: "Hello Alice, you have 42 messages"

LeetCode笔记

1. 队列与栈

1.1 (单调队列) LeetCode.239. 滑动窗口最大值

题目介绍

题目描述

给你一个整数数组 `nums`，有一个大小为 `k` 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 `k` 个数字。滑动窗口每次只向右移动一位。

返回 **滑动窗口中的最大值**。

示例:

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7] 
解释：
滑动窗口的位置                最大值

---------------               -----

[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

1
2
3

示例 2：
输入：nums = [1], k = 1
输出：[1]

提示:

$1 \le \text{nums.length} \le 10^5$
$-10^4 \le \text{nums}[i] \le 10^4$
$1 \le k \le \text{nums.length}$

📝 单调队列 (Monotonic Queue)

核心定义：持续维护队列里面的元素单调递增或单调递减的队列。

💡 如何维护单调递减队列？

维护原则：新元素入队前，清除队尾所有比它小的元素。
根本目的：确保队列头部始终是当前窗口的最大值。
底层逻辑：若新元素 x 大于队尾元素 y，则 y 在 x 离开窗口前永无出头之日（既小又老），故可直接删除 y。

📊 演示范例

输入数组：vec = {1, 3, 1, -1, 2}
(注：在此维护下，队列始终保持递减状态)

操作	动作描述	队列状态 (队首 -> 队尾)	当前最大值
`push(1)`	队空，直接入队	`[1]`	1
`push(3)`	`3 > 1`，弹出 1，入队 3	`[3]`	3
`push(1)`	`1 < 3`，直接入队	`[3, 1]`	3
`push(-1)`	`-1 < 1`，直接入队	`[3, 1, -1]`	3
`push(2)`	`2 > -1` 弹出 -1，`2 > 1` 弹出 1，`2 < 3` 入队 2	`[3, 2]`	3

注意：以上演示暂未考虑滑动窗口大小。如果滑动窗口划走的元素恰好是队列的头元素，则需要把头元素移除。
核心洞察：我们本来就不需要维护当前位置之前、且比当前元素更小的元素，因为在当前元素被替换掉之前，那个更小的元素就已经被“干掉”了。

💻 核心代码实现

1. 单调队列类封装

class monotonic_queue {
public:
    // 入队：维护单调递减性质
    void push(const int& x) {
        // 如果存入的元素比队尾元素大，则将队尾小于x的元素全部移除
        while(!queue.empty() && queue.back() < x) {
            queue.pop_back(); 
        }
        queue.push_back(x);
    } 

    // 出队：如果要移出的元素正是当前最大值（队首），则弹出队首
    void pop(const int &value) {
        if(!queue.empty() && value == queue.front()) {
            queue.pop_front();
        }
    }

    // 获取当前最大值
    int max() {
        return queue.front();
    }

private:
    deque<int> queue; // 使用双向队列
};

2. 滑动窗口构建逻辑 (Main)

int main() {
    monotonic_queue q;
    vector<int> res;
    // 预留空间，避免频繁扩容
    res.reserve(nums.size() - (k - 1));

    // 第一步：先将前 k-1 个元素存入队列
    // 为了保持操作一致性，这里只存 k-1 个元素
    for(int i = 0; i < k - 1; i++) {
        q.push(nums[i]);
    }

    // 第二步：滑动窗口主循环
    // 每次循环执行：①新元素入队 -> ②记录最大值 -> ③移除窗口最左边的元素
    for(int i = k - 1; i < nums.size(); i++) {
        q.push(nums[i]);                 // 新元素入队
        res.push_back(q.max());          // 记录当前窗口最大值
        q.pop(nums[i - (k - 1)]);        // 移除滑出窗口的旧元素
    }
    return res;
}

1.2 (优先级队列(最大最小堆)) LeetCode.347 前 K 个高频元素

题目介绍

类别	难度	喜欢	不喜欢
算法 (Algorithms)	中等 (Medium) 65.72%	2184	-

标签: 哈希表 数组 分治 桶排序 计数 快速选择 排序 堆（优先队列）

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例：

示例 1：

1 2	输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]

示例 2：

1 2	输入: nums = [1], k = 1 输出: [1]

提示：

$1 \le \text{nums.length} \le 10^5$
$-10^4 \le \text{nums}[i] \le 10^4$
$k$ 的取值范围是 $[1, \text{数组中不相同的元素的个数}]$
题目数据保证答案唯一，换句话说，数组中前 $k$ 个高频元素的集合是唯一的

进阶：

你所设计算法的时间复杂度必须优于 $O(n \log n)$ ，其中 $n$ 是数组大小。

📝 优先级队列 (Priority Queue)

核心定义：基于堆 (Heap) 数据结构实现的队列。元素出队顺序不由入队顺序决定，而是由元素的优先级（通常指大小）决定。

💡 如何维护最大堆（默认优先队列）？

核心特性：
- 非先进先出：元素入队顺序不影响出队顺序。
- 自动排序：每次插入或删除元素后，内部会自动调整结构，确保堆顶元素始终是优先级最高（最大或最小）的元素。
- 底层实现：默认使用 std::vector 作为底层容器，通过算法维护堆性质。
维护原则：新元素入队后，通过“上浮”操作调整位置，确保父节点始终大于等于子节点。
底层逻辑：堆是一种完全二叉树结构。对于最大堆，任何节点的值都大于或等于其子节点的值。因此，根节点（top()）必然是全局最大值。插入时只需在末尾添加并向上调整，删除时只需将末尾元素移至根部并向下调整，效率极高。

⚙️ 核心参数与复杂度

1. 模板定义

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

T：存储元素的类型。
Container：底层容器，默认为 std::vector<T>。
Compare：比较规则，默认为 std::less<T>（即最大堆）。

2. 时间复杂度

插入 (push)： O(log⁡N)
删除堆顶 (pop)： O(log⁡N)
获取堆顶 (top)： O(1)

3. 常用成员函数

函数	描述	复杂度
`push(const T& val)`	插入元素并调整堆
`pop()`	删除堆顶元素
`top()`	返回堆顶元素的引用（不删除）
`empty()`	判断队列是否为空
`size()`	返回元素个数

📊 演示范例

输入数组：vec = {1, 3, 1, -1, 2}
(注：这里演示的是 priority_queue<int> 最大堆的入队逻辑)

操作	动作描述	堆内部结构 (逻辑上的完全二叉树)	堆顶 (`top`)
`push(1)`	堆空，直接入队	`[1]`	1
`push(3)`	`3 > 1`，3 上浮成为根，1 下沉	`[3, 1]`	3
`push(1)`	`1 < 3`，1 作为左子节点，无需上浮	`[3, 1, 1]`	3
`push(-1)`	`-1 < 1`，-1 作为右子节点，无需上浮	`[3, 1, 1, -1]`	3
`push(2)`	`2 > -1`，2 上浮替换 -1；`2 > 1`? 否，停止	`[3, 2, 1, -1, 1]`	3
`pop()`	移除堆顶 3，将末尾 1 移至根，向下调整	`[2, 1, 1, -1]`	2

注意：priority_queue 底层通常由 vector 实现，它不保证非堆顶元素的有序性，只保证堆顶是极值。

🛠️ 进阶：底层容器 Container 的选择（参数2）

std::priority_queue 的第二个模板参数 Container 指定了底层用于存储数据的容器。它必须支持随机访问迭代器以及 back(), push_back(), pop_back() 操作。

场景 A：追求极致性能（保持默认 vector）
在 99% 的情况下，不要修改这个参数。std::vector 的连续内存布局使得 CPU 缓存命中率极高，对于堆这种频繁访问父子节点的数据结构，vector 的性能通常优于 deque。
场景 B：避免大规模扩容时的停顿（使用 deque）
如果数据量极大且不可预测，std::vector 在容量不足时会重新分配内存并复制所有元素，这可能导致短暂的延迟抖动。std::deque 按需分配小块内存，不会发生整体复制。

💻 核心代码实战

1. 基础最大堆与最小堆

#include <queue>
#include <vector>
#include <functional> // for std::greater

using namespace std;

// 场景1：默认最大堆 (求前K大，或者动态获取最大值)
void example_max_heap() {
    priority_queue<int> maxHeap; 
    
    maxHeap.push(1);
    maxHeap.push(3);
    maxHeap.push(2);
    
    // 输出: 3, 2, 1
    while(!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
}

// 场景2：最小堆 (求前K小，或者维护Top-K大元素时的辅助堆)
void example_min_heap() {
    // 声明方式：priority_queue<Type, Container, Compare>
    // greater<int> 表示小顶堆
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    minHeap.push(1);
    minHeap.push(3);
    minHeap.push(2);
    
    // 输出: 1, 2, 3
    while(!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
}

2. 经典应用：前 K 个高频元素（也就是本题的问题）

// 场景3：解决 "前 K 个高频元素" (结合 Hash Map)
// 思路：统计频率后，维护一个大小为 K 的【最小堆】
// 为什么是最小堆？因为我们要保留最大的 K 个，所以要把小的踢（pop）出去，
// 堆顶就是这 K 个里最小的，方便比较。
vector<int> topKFrequent(vector<int>& nums, int k) {
     unordered_map<int, int> freqMap;
     for(auto & key : nums){
         freqMap[key]++;
     }
     vector<int> res;
     
     // 用小顶堆，堆顶是当前K个元素中频率最小的
     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;

     for(auto & [key, freq] : freqMap) { // key为数字，freq为出现的频率
         minHeap.push(make_pair(freq, key));
         if(minHeap.size() > k){
             minHeap.pop(); // 弹出当前堆内频率最小的那个
         }
     }
     while(!minHeap.empty()){
         res.push_back(minHeap.top().second);
         minHeap.pop();
     }
     return res;
}

2. 二叉树

2.1：递归遍历（基础）

递归三步曲：
1. 确定递归函数的参数和返回值
2. 确定终止条件
3. 确定单层递归的逻辑
LeetCode：144.前序遍历，145.后序遍历，94.中序遍历

以前序遍历为例：

参数：

 没有必要一次性去确认，需要什么参数加什么，返回值

1	void pre_order(cur,vec);

返回值：

我们的前序遍历是深度优先遍历，一定是遇到null节点的时候返回

所以终止条件是
1
2
3
if(cur == nullptr){
return
}
确定单层递归的逻辑：

// 我们要实现中左右，而当前节点是中（要处理的目标），所以需要对中进行操作逻辑
//  处理中间节点，当前节点需要处理，所以直接走处理逻辑
		vec.emplace_back(node->value);
//	向左遍历：所以需要调用递归（之后需要处理的元素）
		pre_order(node->left_child);
//	向右遍历: 需要调用递归（之后需要处理的元素）
		pre_order(node->right_child);

2.2 二叉树的非递归遍历(迭代法)

非递归就俩类思路，要么就是循环，要么就是循环+栈

2.2.1 前序遍历(Leetcode 94)

此处只展示非递归

vector<int> preorderTraversal(TreeNode *root)
{
    // 非递归法
    // 用栈模拟递归流程
    vector<int> res;
    stack<TreeNode *> m_stack;
    m_stack.push(root);
    while (!m_stack.empty())
    {
        TreeNode *cur = m_stack.top();
        m_stack.pop();
        if (cur == nullptr)
        {
            continue;
        }
        res.push_back(cur->val);
        // 栈是先访问后进的元素，前序是中左右，所以需要先进右后进左
        m_stack.push(cur->right);
        m_stack.push(cur->left);
    }
    return res;
}

注意，这里是先处理中节点后，将右节点先入栈，左节点后入栈，因为栈是FILO结构，先左，则左后进

2.3.2 后序遍历(Leetcode 145）

已知前序遍历的结果是中左右，如果在上一题中调换right和left的入栈顺序，就可以得到中右左的结果，倒置，则为左右中

vector<int> postorderTraversal(TreeNode* root) {
    // 非递归法
    // 用栈模拟递归流程
    vector<int> res;
    stack<TreeNode *> m_stack;
    m_stack.push(root);
    while (!m_stack.empty())
    {
        TreeNode *cur = m_stack.top();
        m_stack.pop();
        if (cur == nullptr)
        {
            continue;
        }
        res.push_back(cur->val);
        // 栈是先访问后进的元素,左先进，则左后出，达成中右左
        m_stack.push(cur->left);
        m_stack.push(cur->right);
    }
  	// 中右左倒置则为左中右
    reverse(res.begin(),res.end());
    return res;
}

2.3.3 中序遍历(Leetcode 94)

题目链接

有个很反常识的点是，中序遍历的代码要比前序和后序难得多，这是有个很难受的原因

我们可以发现，之前我们处理的方案，都是优先去访问中节点，拿到中节点的结果（无论中节点该在前还是在后），这就代表，最起码我们当前访问的节点的数据，当前必然能遇到
但是中序遍历她不一样，她第一个访问的必定是最左下角的元素，即使倒置，第一个访问的也是最右下角的元素，这个元素和我们的根节点是没有关系的

这就要求着我们必须要保证我们当前访问的元素，一定是剩余未访问节点的最左下角，才能得到中序遍历的答案

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* curr = root;

    while(curr || !s.empty()){
        while(curr)
        {   
            // 所有左子树入栈
            s.push(curr);
            curr = curr->left;
        }
        // 处理栈中元素
        curr = s.top();
        s.pop();
        res.push_back(curr->val);

        // 转向右子树(如果当前节点右右子树，则处理中节点后，优先处理右子树的内容)
        curr = curr-> right;
    }
    return res;
}

2.3.4 后序遍历如果不借助前序遍历倒置的话，该怎么做？（小拓展）

~~是啊，该怎么做？~~

咳咳，开玩笑的，那就只能参考中序遍历的处理方式来思考了

既然我们的中节点被放在了最低优先级，那在我们处理当前节点时，必须确保所有的子节点都已经处理了。

在之前我们处理中序遍历的流程中，遍历到最左节点的时候，此时的元素，可能会有右节点（对于右节点来说，我们当前的节点是中节点，优先级更低）

所以需要添加检查右节点的逻辑

但是有个很大的问题是，这里会有一个逻辑闭环：

对于一个节点A，检查右节点B，如果没有，就优先处理右边
右边的节点B处理完后（即右边的左右孩子都已得到处理）再处理节点A
对于一个节点A，检查右节点B，如果没有，就优先处理右边
右边的节点B处理完后（即右边的左右孩子都已得到处理）再处理栈里拿出来的节点A
………….

所以我们必须得知道上一个处理的到底是哪个节点！又因为右子树满足左右中遍历顺序，所以右子树最后遍历的节点肯定是中节点。我们只需要记录上一个遍历的节点是哪个即可，如果上一个节点是自己的右子树，那就没必要再加入栈，优先处理右节点了

这时的逻辑就成了：
1. 对于一个节点A，检查右节点B，如果没有，就优先处理右边
2. 右边的节点B处理完后（即右边的左右孩子都已得到处理）再处理节点A
3. 对于一个节点A，检查右节点B，B是上一个处理的节点，无需再处理，直接处理A

这样逻辑闭环就解开了，我们就可以按顺序遍历完所有的节点！

vector<int> postorderTraversal(TreeNode* root) {
    // 迭代法：后序遍历（左→右→中）
    // 核心难点：需要判断右子树是否已处理完毕
    // 解决方案：使用 prev 指针记录上一个访问的节点
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* curr = root;
    TreeNode* prev = nullptr;  // 记录上一个访问的节点

    while (curr != nullptr || !s.empty()) {
        // 第一步：将所有左子节点入栈
        while (curr != nullptr) {
            s.push(curr);
            curr = curr->left;
        }

        // 第二步：查看栈顶节点（但不弹出）
        curr = s.top();

        // 第三步：判断是否可以访问当前节点
        // 条件1：没有右子树
        // 条件2：右子树已经访问过（prev == curr->right）
        if (curr->right == nullptr || curr->right == prev) {
            // 可以访问当前节点
            s.pop();
            res.push_back(curr->val);
            prev = curr;      // 更新 prev
            curr = nullptr;   // 防止重复处理左子树
        } else {
            // 右子树未处理，转向右子树
            curr = curr->right;
        }
    }
    return res;
}

2.3.5 层序遍历(Leetcode 102)

题目链接

vector<vector<int>> levelOrder(TreeNode* root) {
    queue<TreeNode*> que;
    vector<vector<int>> res;
    if (root != nullptr) que.push(root);
    while (!que.empty()) {
        vector<int> tmp;
        for(int i = que.size(); i > 0; --i) {  // 第一次写没写出来
            root = que.front();
            que.pop();
            tmp.push_back(root->val);
            if (root->left != nullptr) que.push(root->left);
            if (root->right != nullptr) que.push(root->right);
        }
        res.push_back(tmp);
    }
    return res;
}

时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次。
空间复杂度 O(N) ：最差情况下，即当树为平衡二叉树时，最多有 N/2 个树节点同时在 queue 中，使用 O(N) 大小的额外空间。

2.4 一些典型的二叉树问题

2.4.1 翻转二叉树 (Leetcode 226)

题目详情
- 题目链接
这道题可以理解为对所有节点进行左右孩子的交换
- 但是，遍历方式有讲究
- 中序遍历是不好做的
因为中序遍历我们在处理右孩子前，对中节点进行了左右节点互换，导致右孩子变成了左孩子，无法达到预期

解决方案：

TreeNode* invertTree(TreeNode* root) {
    if(root == nullptr) return nullptr;
    invertTree(root->left);
    swap(root->left, root->right);
    invertTree(root->left);

    return root;
}

2.4.2 对称二叉树 (Leetcode 101)

题目链接

代码记录其实俩种思路基本一个意思，解法2看起来会更明确，更像后序遍历
- 此题的重点是要想明白该用什么遍历解决问题，我们在判断当前节点是否是对称二叉树的时候，必须要知道自己的所有子树是否对称，需要知道左右子树的条件，所以这种情况需要用后序遍历
- 适用场景: 当前节点的处理依赖于左右子树的计算结果
  - 类似的：
    - 前序遍历：当前节点的处理不依赖子节点，但需要向所有子节点传递信息
    - 中序遍历：需要按特定顺序访问节点,通常用于BST或生成有序序列，常用于BST的结果排序（升序）
    - 层序遍历：需要按层依次处理节点，例如求树的最小深度

class Solution {
public:
    // 分治+短路求值？
    bool isSymmetricFunc(TreeNode* left,TreeNode* right)
    {
        if(left==nullptr&&right==nullptr){
            return true;
        }
        if(left!=nullptr && right!=nullptr){
            return left->val == right->val && isSymmetricFunc(left->left,right->right) && isSymmetricFunc(left->right,right->left);
        }
        else
        {
            return false;
        }
    }
    bool isSymmetric(TreeNode* root) {
        return isSymmetricFunc(root->right,root->left);
    }
    // 后序遍历？
    bool  post_order (TreeNode* left,TreeNode* right)
    {
        if (left != nullptr && right != nullptr)
        {
            bool condition1 = post_order(left->left, right->right); // 判断左节点的左子树与右节点的右子树对称
            bool condition2 = post_order(left->right, right->left); // 判断左节点的右子树和右节点的左子树对称
            return condition1 && condition2 && left->val == right->val; // 单个节点内处理逻辑：判断左右节点相等并且左右子树对称 (当前节点是对称二叉树的充要条件)
        }
        else if (left == nullptr && right == nullptr){
            return true;
        }
        else
        {
            return false;
        }
    }
    bool isSymmetric1(TreeNode* root) 
    {
        return post_order(root->left,root->right);
    }
};

2.4.3 二叉树的最大深度(Leetcode 104)

二叉树的最大深度

int maxDepth(TreeNode* root) {
  	if (!root) return 0;
    return max(maxDepth(root->right), maxDepth(root->left)) + 1;
}

也是一种后序处理思路

2.4.4 二叉树的最小深度 (LeetCode 111)

题目链接

📌 核心思路

本题的关键在于遍历方式的选择对效率的影响:

DFS (前/中/后序): 必须遍历完整棵树才能确定最小深度,无法有效剪枝
BFS (层序遍历): 利用层级特性,遇到第一个叶子节点立即返回,实现天然剪枝

🔴 重点: BFS 在”浅层存在叶子节点”的场景下,性能远优于 DFS!

🔍 两种解法对比

方案1: DFS 后序遍历 (基础解法)

cpp

int minDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    
    // 叶子节点
    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }
    
    // 只有右子树: 必须继续往下走
    if (root->left == nullptr) {
        return 1 + minDepth(root->right);
    }
    
    // 只有左子树: 必须继续往下走
    if (root->right == nullptr) {
        return 1 + minDepth(root->left);
    }
    
    // 左右子树都存在: 取较小值
    return 1 + min(minDepth(root->left), minDepth(root->right));
}

问题分析:

❌ 最坏情况: 完全二叉树需遍历所有节点 O(n)
❌ 无法提前终止: 即使左子树深度为1,仍会完整遍历右子树
❌ 递归开销: 每层函数调用都有栈帧分配

方案2: BFS 层序遍历 (优化解法) ✅

cpp

int minDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    
    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    
    while (!q.empty()) {
        ++depth;
        int levelSize = q.size();
        
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();
            
            // 🎯 核心优化: 遇到第一个叶子节点立即返回
            if (node->left == nullptr && node->right == nullptr) {
                return depth;
            }
            
            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
    }
    
    return depth;
}

优势分析:

✅ 提前终止: 找到第一个叶子即返回,无需遍历整棵树
✅ 时间复杂度: O(k),k为最小深度对应的节点数(通常 k << n)
✅ 空间复杂度: O(w),w为树的最大宽度

📊 性能对比示例

假设树结构如下:

      1
     / \
    2   3     ← 第2层,节点3是叶子
   / \
  4   5
 /
6             ← 第4层,节点6是叶子

遍历方式	访问节点数	说明
DFS 后序	6个	必须遍历完整棵树才能确定最小深度=2
BFS 层序	3个	遇到节点3立即返回,减少50%计算量 ✅

💡 关键要点总结

💡 维护原则:

何时选择 BFS:
- 求最小深度、最短路径等”首次遇到即最优”的问题
- 树的宽度远小于高度时(BFS队列开销小)
- 需要按层级处理节点的场景
何时选择 DFS:
- 需要遍历所有节点或所有路径的问题
- 树的高度较浅时(递归栈开销小)
- 需要自底向上汇总信息的场景(如对称性判断)
BFS 剪枝技巧:
- 利用 levelSize 控制层级边界
- 在循环内部检查终止条件,找到即返回
- 避免使用额外变量记录全局最优值

2.4.5 完全二叉树的节点数

在完全二叉树中:
- 如果 最左侧深度 == 最右侧深度 → 说明最后一层也是满的 → 整棵树是满二叉树
- 如果 最左侧深度 > 最右侧深度 → 说明最后一层不满 → 需要递归处理
为什么?
- 完全二叉树的定义保证了”最后一层节点靠左排列”
- 如果最右侧深度等于最左侧深度,说明最后一层已经填满
- 此时整棵树满足满二叉树的定义

int isFullTree(TreeNode* node){
    TreeNode* left = node->left;
    TreeNode* right = node->right;
    int height = 1;
    while(left!= nullptr && right != nullptr) // 如果当前树最左边和最右边的叶子结点高度相同，有因为本来是完全二叉树，所以是满二叉树（最后一层最右侧的叶子结点的 `左边同层的叶子结点` 是必定存在的）
    {
        left = left->left;
        right = right->right;
        height++;
    }
    if(left == nullptr && right == nullptr){
        return height;
    }
    else
    {
        return 0;
    }
}
int countNodes(TreeNode* root) 
{   
    if(root == nullptr){
        return 0;
    }
    if(int high = isFullTree(root)){ //哇噢？ 我也是第一次这么写，原来里面能读到high！
        return (1 << high) - 1;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

2.5 二叉搜索树

2.5.1 二叉搜索树的插入

题目链接： leetcode.701 二叉搜索树的插入

一开始的错误思路： 找到比所需要插入的值小的最大值的位置 min_pointer，根据插入值val创建新节点 new_node

如果找到了，
- 如果该位置的右侧有节点，将该位置右侧的节点放在new_node的右侧 new_node作为min_pointer的右节点
  1
  2
  3
  4
  if(min_pointer->right){
  new_node->right = min_pointer->right;
  min_pointer->right = new_node;
  }
- 如果右侧没结点，则在右侧新增节点new_node
如果没找到，从头结点，找到最左边节点，令其左孩子为 new_node

这样做太麻烦了，而且时间复杂度很高(只能击败0.82%)，时间复杂度为 $ O(n) $

我们应该直接搜索该元素，当搜到nullptr的时候，代表该位置可插入才对，因为要把叶子结点的结果传给父节点，所以需要用后序遍历

//1. 迭代法：
TreeNode* InsertBST(TreeNode* root, int val)
{
	TreeNode* new_node = new TreeNode(val);
  if(!root){
      return new_node;// 如果给的树为空，需要额外处理一下
  }
  TreeNode* curr = root;
  while(true)
  {
  		if(curr->val > val){// 当前节点大于目标值，向左找
        	if(!curr->left)
          {
            curr->left = new_node;
            break;
          }
	        curr = curr->left;  
      }
    	else if(curr->val < val){
        	if(!curr->right)
          {
            curr->right = new_node;
	          break;        	
          }
	        curr = curr->right  
      }
    	else{
        break;
      }
  }
  return root;
}
// 2. 递归法
TreeNode* insertIntoBST(TreeNode* root, int val){
  	if(!root){
      // 如果root为空，则说明找到了该创建节点的地方
      return new TreeNode(val);
    }
  	if(root->val > val){// 目标值更小，在左子树中寻找结果
      root->left = insertIntoBST(root->left,val); // 直接赋值，编译器会优化，其实效率会更高，如果写多余的if判断，效率会低一点（神奇！）
    }
  	else if(root->val < val){
      root->right = insertIntoBST(root->right,val);
    }
  	return root; // 返回当前正在遍历的节点，不影响逻辑，但是在处理过程中会多余很多次赋值？
}

2.5.2 二叉搜索树的删除节点

题目链接： Leetcode.450 二叉搜索树的删除节点

1.迭代法：哨兵节点(对所有节点处理一致化)

2.递归法：

//递归法：
    TreeNode* Trasalval(TreeNode* root, int key)
    {
        if(!root){
            // 如果没找到该节点
            return nullptr;
        }
        if(root->val < key){
            root->right = Trasalval(root->right,key);// 向右子树迭代
        }
        else if(root->val > key){
            root->left = Trasalval(root->left,key);
        }
        else{
            // 当前节点是目标节点，需要删除
            //分情况讨论
            if(!root->left && !root->right){ // 叶子节点
                // 该节点不需要，所以删除，return nullptr
                delete root;
                root = nullptr;
                return nullptr;
            }
            else if(!root->left && root->right || root->left && !root->right){ //左右节点中有一个为nullptr
                TreeNode* tmp = root->right? root->right : root->left;
                delete root;
                root = nullptr;
                return tmp;
            }
            else{ // 左右节点同时存在，需要额外处理
                // 找到当前节点的左侧最大节点，将当前节点的右子树作为左侧最大节点的右子树（也可以反过来）
                TreeNode* tmp = root->right;
                TreeNode* new_root = root->left;
                TreeNode* curr = root->left;
                while(curr->right){
                    curr = curr->right;
                }
                curr->right = tmp;
                delete root;
                root = nullptr;
                return new_root;
            }
        }
        return root;
    }

妙手：root->left = Trasalval(root->lefft,key)

可以把后序遍历的递归过程认为成一个链接的过程，关键步骤为 root->left = Trasalval(root->lefft,key) 每个递归的结果都会传给root，所以想要跳过的节点就可以直接忽略当前节点，返回你想要该位置是什么节点，图上，例如返回new_root,就是将new_root与上层递归的父节点链接在一起与此同时，当需要删除的节点为根节点的时候，这个处理模式下，会走该节点不需要的逻辑，删除root，返回nullptr，符合题意递归法甚至看起来要比迭代法更简单呢！ ## 3. 回溯算法 ### 3.1 理论基础回溯和递归的关系：回溯和递归是相辅相成的，只要有递归，就会有回溯，回溯通常会隐藏在递归函数下面，回溯法是一个纯暴力的搜索方法，不是什么高效的算法 ### 3.2 能解决的问题： * **组合问题**：例： 1 2 3 4，找出能大于3的组合（没有顺序） * **切割问题**：给一个字符串，问有几种切割的方式？如何切割才能让子串是串回文串 * **子集问题：** 1,2,3,4 的子集 * **排列问题：** 例 1,2,3,4 找出能排列的方式（有顺序） * **棋盘问题：** N皇后，解数独以上这些问题用传统的for循环嵌套是很难解决的，必须要用回溯搜索法来解决 > 纯暴力解决如何组合，如何切割，找到他的子集，找到排列组合，找到所有的棋盘情况 > > 就是一种，暴力的搜索方式

如果想要清晰的了解回溯法的话，最好是把回溯法抽象为一个图形结构，这会有助于我们的理解，也有助于我们用这种思维方式去解决这些问题。靠大脑去模拟是特别困难的

回溯法通常都可以抽象为一个N叉树，一般来说这棵树的宽度就是我们在回溯法中处理的集合的大小，树的深度就是递归的深度

3.3 回溯法的模板：

一般来说回溯法的递归函数都是没有返回值的，一般起名为BackTrackcing

参数一般会比较多，不太容易在一开始的时候就能确认所有参数，写逻辑的时候遇到了想用什么数据，添加参数即可

终止条件一般都是收集结果的时候

回溯法的抽象结构 )

void BackTracking(参数){
  if(终止条件){
  	// 一般来说终止条件是收集结果的时候(叶子结点的时候)
    return;
  }
  // 单层搜索逻辑：
  for(集合的元素集(单节点的所有子节点)){
    // 处理节点
    // 递归函数(在树形图里往下走到下一级)
    // 回溯操作(撤销处理节点的情况）
  }
}

3.4 对应的问题解决：

3.4.1 组合问题：

3.4.1.1 77.组合

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void BackTracking(int n, int k, int begin)
    {
        // 输出条件，path存满k个元素则输出
        if(path.size() == k)
        {
            res.emplace_back(path);
            return;
        }
        // 在path还需要取 k - path.size()时， 如果剩余可取数字 n - i + 1 不足，则剪枝
        for(int i = begin; n - i + 1>= k - path.size();i++)
        {
            path.push_back(i);
            BackTracking(n,k,i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        BackTracking(n,k,1);
        return res;
    }
};

3.4.1.2 216.组合总和 III

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void BackTracking(int k,int n,int StartNum, int sum)
    {
        if(path.size() == k)
        {
            // sum为n时输出结果
            if(sum == n){
                res.push_back(path);
            }
            return;
        }
      	// 在循环流程中添加对sum的维护，剪枝逻辑本质上没修改
        for(int i = StartNum;10 - (k-path.size()) >= i && sum <= n;i++)
        {
            path.push_back(i);
            sum = sum + i;
            BackTracking(k,n,i + 1,sum);
            sum = sum - i;
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        BackTracking(k,n,1,0);
        return res;
    }
};

3.4.1.3 17.电话号码的字母组合

class Solution {
public:
    unordered_map<char, vector<char>> telephone_num_map = {// 一个电话按键表 char to vector<char>
        {'2', {'a', 'b', 'c'}}, 
        {'3' , {'d', 'e', 'f'}}, 
        {'4', {'g', 'h', 'i'}}, 
        {'5', {'j', 'k', 'l'}}, 
        {'6', {'m', 'n', 'o'}}, 
        {'7', {'p', 'q', 'r', 's'}}, 
        {'8', {'t', 'u', 'v'}}, 
        {'9', {'w', 'x', 'y', 'z'}}
    };
    vector<string> res;
    void BackTracking(const string &digits,int start_index, vector<char> &path)
    {
        if(digits.size() == path.size())
        {
            res.emplace_back(path.begin(), path.end());
            return;
        }
        int size = digits.size();
	      // 本题不需要剪枝，需要遍历的次数是有限而且完全的，例如“5,6,7” 对应字母分别为3,3,4个 所以一共是3*3*4 = 36种结果
        for(auto & v : telephone_num_map[digits[path.size() -1]])
        {
            path.push_back(v);
            BackTracking(digits,path.size() - 1, path);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<char> path;
        BackTracking(digits,0,path);
        return res;
    }
};

3.4.1.4 39.组合总和

该题区别于之前组合问题的最大区别就是，同一个元素可以多次使用，例如：如case中：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

其中 2 是可以多次使用的

考虑该问题，我们需要在进入递归时，再次考虑当前元素是否能满足条件也就是说i不能+1：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    int sum = 0;
    void BackTracking(vector<int>& candidates, int target,int start_index){
        if(sum == target)
        {
            res.emplace_back(path);
            return;
        }
        for(int i = start_index; i < candidates.size();i++){
            sum += candidates[i];
            path.push_back(candidates[i]);
            if(sum <= target){
                // 注意，这里就是和组合总和iii 最大的区别，直接传入i而不是i+1
                BackTracking(candidates,target,i);
            }
            sum -= candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        BackTracking(candidates,target,0);
        return res;
    }
};

3.4.1.5 40.组合总和 II

该题的相对于普通组合总和问题来说，最大的区别是：该集合中元素是会重复的，例如[10,1,2,7,6,1,5] 其中有俩个1，每个1只能使用一次，是不同的元素

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    int sum = 0;
    void BackTracking(vector<int>& candidates, int target,int start_index,vector<int>& used_vec){
        // 难点：怎么去重？
        // 一开始错误的思路：

        // for(int i = start_index; i < candidates.size();i++){
        //     sum += candidates[i];
        //     path.push_back(candidates[i]);
        //     if(sum <= target)
        //     {
        //         BackTracking(candidates,target,i+1);
        //     }
        //     sum -= candidates[i];
        //     path.pop_back();
        // }
        //---------------------------//---------------------------
        // Your Input
        // [10,1,2,7,6,1,5]、、、
      
        // 8
        // Output：
        // [[1,2,5],[1,7],[1,6,1],[2,6],[2,1,5],[7,1]]
        // Expected Answer
        // [[1,1,6],[1,2,5],[1,7],[2,6]]
 	      //---------------------------//---------------------------
        // 不对！ 同样数值的不同元素，可能被多次使用，答案是错的
        // 需要考虑如何去重
        // 去重思路：  考虑 如果第一个元素选择了 某个元素A(值为a)，其递归树包含的结果，已经包含了第一个元素选择B(值为a）的所有结果，所以我们只会在选择中，对于相同值的元素，只选择其中一个一次，之后就不再在同级递归树中再次选择
				// 也就是树层去重
        // 使用过的元素，就不再使用了，避免重复
        // 树层去重 （形象比喻，非专业术语）广度上的去重，同一元素会多次取,本题关键点
        // 树枝去重 （形象比喻，非专业术语) 深度上的去重，同一元素只取一次
        if(sum == target)
        {
            res.emplace_back(path);
            return;
        }
        // candidates = [1,1,2,5,6,7,10]
        for(int i = start_index; i < candidates.size();++i)
        {
          	// 与组合总和iii 最大的区别，如果当前元素不是第一个元素，且上一个元素和当前元素相同，且上一个元素没有使用（也就是不在上个元素的子递归树中，而是同级的再开一个新递归树，那就continue掉，因为新开的递归树的结果已经在处理上个相同元素的时候已经包含了（如下图例）
            if(i > 0 && candidates[i] == candidates[i-1] &&used_vec[i-1] == 0)
            {
                continue;
            }
            sum += candidates[i];
            path.push_back(candidates[i]);
            used_vec[i] = 1;
            if(sum <= target)
            {
                BackTracking(candidates,target,i+1,used_vec);
            }
            sum -= candidates[i];
            path.pop_back();
            used_vec[i] = 0;
        }
    }
  	// [10,1,2,7,6,1,5]
		// 8
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> used_vec(candidates.size());  
        sort(candidates.begin(),candidates.end()); // 先对数组进行排序，之后去重剪枝需要用到 
        // [1,1,2,5,6,7,10]
        BackTracking(candidates, target, 0,used_vec);
        return res;
    }
};

图解重复的情况

所以，遍历到第二个1的时候，如果发现之前上一个元素不是1，就是一种重复的情况，需要剔除掉

3.4.2 切割字符串问题

3.4.2.1 131. 分割回文串

class Solution
{
public:
    // 用于判断传入参数是否是回文串的函数
    bool isPalindrome(const string &a)
    {
        int size = a.size();
        if (size == 0)
        {
            return false;
        }
        if (size == 1)
        {
            return true;
        }
        for (int i = 0, j = a.size() - 1; i < j; i++, j--)
        {
            if (a[i] != a[j])
            {
                return false;
            }
        }
        return true;
    }

    vector<vector<string>> res;
    vector<string> path;
    void BackTracking(string s, int start_index)
    {
        if (start_index >= s.size())
        {
            res.push_back(path);
            return;
        }
        for (int i = start_index; i < s.size(); ++i)
        {
            string tmp_str = s.substr(start_index, i - start_index + 1);
            // 对于  aabbaa
            // 此处每次循环tmp_str的取值：
            // a-> aa -> aab -> aabb-> aabba -> aabbaa 其中 aab,aabb,aabba都不是回文串，会被continue掉
            // 如果tmp_str不是回文串，就不需要处理了，continue掉，直到他是回文串
            if(!isPalindrome(tmp_str)){
                continue;
            }
            path.push_back(tmp_str);
            // 如果是a时，进入下一轮  则对于下一次BackTracking  判断的是：
            // 剩余子串 abbaa是不是回文串  有 a->ab-> abb-> abba ->  abbaa   其中有 a和 abba是回文串，能进下一层递归的BackTracking
            BackTracking(s, i + 1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s)
    {
        BackTracking(s, 0);
        return res;
    }
};

3.4.2.2 93.复原 IP 地址

本题类似于上一题，只不过上一题是判断回文串，这个是判断分成四份的情况下，每份是否是符合IP地址的格式

class Solution {
public:
    // 判断传入str是否为IP地址，是的话，返回true
    bool is_valid_ip_part(const string & str)
    {
        int len = str.size();
        if(len == 0 || len > 3){
            return false;
        }
        if(len > 1 && str[0] == '0'){
            return false;
        }
        if(len == 3)
        {   
            if(stoi(str) > 255) return false;
        }
        return true;
    }
    vector<string> res;
    vector<string> path;
    void backTracking(string s, int start_index)
    {
        if(path.size() == 4 && start_index == s.size()){
            res.push_back(path[0] + '.' + path[1] + '.' + path[2] + '.' + path[3]);
            // 直接拼接效率更高，也可以参考说明介绍： 编码问题记录中的 9 ~ 11 会有更好的拼接方法
            // string_view,join,std::format
            return;
        }
        if(path.size() >= 4){ // 分成4份，所以不能大于4份
            return;
        }
        for(int i = start_index;i< s.size()&& i <=3 + start_index;i++)
        {
            string tmp_str = s.substr(start_index,i - start_index + 1);
            if(!is_valid_ip_part(tmp_str)){
                continue;
            }
            path.push_back(tmp_str);
            backTracking(s,i + 1);
            path.pop_back();
        }

    }
    vector<string> restoreIpAddresses(string s)
    {
        if (s.size() < 4 || s.size() > 12) return res; // 不能分为4份的情况
        backTracking(s,0);
        return res;
    }
};

3.4.2.1 和3.4.2.2 本质上是一模一样的问题，只不过变了表现方式而已

3.4.3 子集问题：

3.4.3.1 78. 子集

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;

    void BackTracking(vector<int> & nums, int start_index)
    {
        res.push_back(path);  // 收集结果不一样，要把过程中的path全部放入结果集中
        for(int i = start_index;i <nums.size();i++)
        {
            path.push_back(nums[i]);
            BackTracking(nums,i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        BackTracking(nums, 0);    
        return res;
    }
};

graph TD
    %% 定义样式
    classDef root fill:#f9f,stroke:#333,stroke-width:2px;
    classDef node fill:#fff,stroke:#333,stroke-width:1px;
    classDef leaf fill:#e1f5fe,stroke:#0277bd,stroke-width:1px;
    
    START((Start)) --> N_EMPTY["[]"]:::root
    
    %% 第一层分支
    N_EMPTY -- "选 1" --> N_1["[1]"]:::node
    N_EMPTY -- "选 2" --> N_2["[2]"]:::node
    N_EMPTY -- "选 3" --> N_3["[3]"]:::node
    
    %% 第二层分支 (从1出发)
    N_1 -- "选 2" --> N_12["[1, 2]"]:::node
    N_1 -- "选 3" --> N_13["[1, 3]"]:::node
    
    %% 第二层分支 (从2出发)
    N_2 -- "选 3" --> N_23["[2, 3]"]:::node
    
    %% 第三层分支 (从1,2出发)
    N_12 -- "选 3" --> N_123["[1, 2, 3]"]:::leaf


    %% 关联样式
    linkStyle default stroke-width:1px,fill:none,stroke:black;

由图片可以看出来，每次递归中的path都需要存储起来！

3.4.3.2 90. 子集 II

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;

    void BackTracking(vector<int> & nums, int start_index, vector<bool> used_vec)
    {
        res.push_back(path);  // 收集结果不一样，要把过程中的path全部放入结果集中
        for(int i = start_index;i <nums.size();i++)
        {
            if(i>0 && nums[i] == nums[i-1] && used_vec[i-1] == 0) // 和组合问题一样，同样元素递归树是重复的，再次遍历到则忽略
            {
                continue;
            }
            used_vec[i] = true;
            path.push_back(nums[i]);
            BackTracking(nums,i + 1, used_vec);
            used_vec[i] = false;
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<bool> used_vec(nums.size());
        BackTracking(nums, 0, used_vec);    
        return res;
    }
};

flowchart TD
    %% 样式定义
    classDef root fill:#f5f5f5,stroke:#333,stroke-width:2px;
    classDef valid fill:#e8f5e9,stroke:#2e7d32,stroke-width:1px;
    classDef pruned fill:#ffebee,stroke:#c62828,stroke-width:1px,stroke-dasharray: 5 5;
    classDef leaf fill:#fff9c4,stroke:#fbc02d,stroke-width:1px;

    Root["[]"]:::root

    %% === 第一层：startIndex=0 ===
    Root -- "取 nums[0]=1" --> N1["[1]"]:::valid
    Root -- "❌ 跳过 nums[i-1]= nums[i]  且i-1的元素未使用" --> N1_Dup["[1] (重复)"]:::pruned
    Root -- "取 nums[2]=2" --> N2["[2]"]:::valid
    Root -- "取 nums[3]=3" --> N3["[3]"]:::valid

    %% === 被剪枝的完整子树（如果不跳过，会产生这些重复） ===
    N1_Dup -- "取 nums[2]=2" --> Dup_1_2["[1,2] (重复)"]:::pruned
    N1_Dup -- "取 nums[3]=3" --> Dup_1_3["[1,3] (重复)"]:::pruned
    Dup_1_2 -- "取 nums[3]=3" --> Dup_1_2_3["[1,2,3] (重复)"]:::pruned

    %% === 第二层：基于 [1] (startIndex=1) ===
    N1 -- "取 nums[1]=1<br/>i=1==start=1 允许" --> N1_1["[1,1]"]:::valid
    N1 -- "取 nums[2]=2" --> N1_2["[1,2]"]:::valid
    N1 -- "取 nums[3]=3" --> N1_3["[1,3]"]:::valid

    %% === 第三层：基于 [1,1] (startIndex=2) ===
    N1_1 -- "取 nums[2]=2" --> N1_1_2["[1,1,2]"]:::valid
    N1_1 -- "取 nums[3]=3" --> N1_1_3["[1,1,3]"]:::valid

    %% === 第四层：基于 [1,1,2] (startIndex=3) ===
    N1_1_2 -- "取 nums[3]=3" --> N1_1_2_3["[1,1,2,3]"]:::leaf

    %% === 第三层：基于 [1,2] (startIndex=3) ===
    N1_2 -- "取 nums[3]=3" --> N1_2_3["[1,2,3]"]:::leaf

    %% === 第二层：基于 [2] (startIndex=3) ===
    N2 -- "取 nums[3]=3" --> N2_3["[2,3]"]:::leaf

    %% === 第二层：基于 [3] (startIndex=4) ===
    N3 -- "循环结束<br/>i=4>=len=4" --> End1["终止"]:::pruned

3.4.3.3 491.非递减子序列

这道题与之前的 3.4.3.1 78.组合总和II 和 3.4.3.2 90.子集II 有很明确的区别，思路不能沿用，因为数组需要保持有序性，不可以提前排序，但仍然要去重，这里可以引出一个新的树层去重方式

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;

    void BackTracking(vector<int> & nums, int start_index)
    {
        if(path.size()>1) res.push_back(path);  // 收集结果不一样，要把过程中的path全部放入结果集中
        bool used[201] = {false};  // 题目要求[-100,100] nums范围，所以用位图存储，效率最高
      	// unorded_set<int> used;
        for(int i = start_index;i <nums.size();i++)
        {
            if(!path.empty() && path.back() > nums[i]){
                continue;
            }
            if(used[100 + nums[i]]){ // 同层内的重复 不再继续处理
                continue;
            }
          	// if(used.find(nums[i]) != used.end()) continue;
            path.push_back(nums[i]);
            used[100 + nums[i]] = true;
            // used.insert(nums[i]);
            BackTracking(nums,i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        BackTracking(nums, 0); 
        return res;
    }
};

我们知道BackTracking每进入一次，相当于逻辑树向下一层，我们要做的是同层去重，所以可以在没有进入BackTracking的同层创建变量used 就能知道该元素在本层内是否多次使用了，这样可以避免同层内取同值元素

graph TD
    Root["[4, 6, 7, 7]"]
    
    Root --> N1["路径: [4]"]
    Root --> N2["路径: [6]"]
    Root --> N3["路径: [7] (第1个)"]
    Root -.-> N4["❌ 路径: [7] (第2个)<br/>同层重复，剪枝"]

    N1 --> N1_1["路径: [4, 6]"]
    N1 --> N1_2["路径: [4, 7] (第1个)"]
    N1 -.-> N1_3["❌ 路径: [4, 7] (第2个)<br/>同层重复，剪枝"]

    N1_1 --> N1_1_1["路径: [4, 6, 7] (第1个) ✅ 收集"]
    N1_1 -.-> N1_1_2["❌ 路径: [4, 6, 7] (第2个)<br/>同层重复，剪枝"]

    N1_2 --> N1_2_1["路径: [4, 7, 7] ✅ 收集"]

    N2 --> N2_1["路径: [6, 7] (第1个) ✅ 收集"]
    N2 -.-> N2_2["❌ 路径: [6, 7] (第2个)<br/>同层重复，剪枝"]

    N3 --> N3_1["路径: [7, 7] ✅ 收集"]

    style N4 fill:#ffebee,stroke:#c62828,stroke-dasharray: 5 5
    style N1_3 fill:#ffebee,stroke:#c62828,stroke-dasharray: 5 5
    style N1_1_2 fill:#ffebee,stroke:#c62828,stroke-dasharray: 5 5
    style N2_2 fill:#ffebee,stroke:#c62828,stroke-dasharray: 5 5
    
    style N1_1_1 fill:#e8f5e9,stroke:#2e7d32
    style N1_2_1 fill:#e8f5e9,stroke:#2e7d32
    style N2_1 fill:#e8f5e9,stroke:#2e7d32
    style N3_1 fill:#e8f5e9,stroke:#2e7d32

TodoList

编码问题记录

1.你的代码问题在于:每次拼接字符串时都创建了新对象:

💡 额外的小建议：拼接字符串的方式

2.简化 pair 构造语法

3.用位运算替代 $2^n$

4.动态的容器的大小不可以放在for循环中

5. 哨兵节点 (对所有结点处理一致化)

6. LeetCode 里不需要手动delete

7.vector的删除

8. String的删除

8.1. erase()：精准外科手术（核心删除方法）

8.2. pop_back()：末端快删（轻量级删除）

8.3. remove() + erase()：批量删除的黄金组合

8.4. 总结

9. string_view (C++17 引入)：零拷贝的字符串“放大镜”

10. join 思想：告别低效的循环拼接

11. std::format (C++20)：类型安全的格式化神器

LeetCode笔记

1. 队列与栈

1.1 (单调队列) LeetCode.239. 滑动窗口最大值

📝 单调队列 (Monotonic Queue)

1.2 (优先级队列(最大最小堆)) LeetCode.347 前 K 个高频元素

📝 优先级队列 (Priority Queue)

2. 二叉树

2.1：递归遍历（基础）

2.2 二叉树的非递归遍历(迭代法)

2.2.1 前序遍历(Leetcode 94)

2.3.2 后序遍历(Leetcode 145）

2.3.3 中序遍历(Leetcode 94)

2.3.4 后序遍历如果不借助前序遍历倒置的话，该怎么做？（小拓展）

2.3.5 层序遍历(Leetcode 102)

2.4 一些典型的二叉树问题

2.4.1 翻转二叉树 (Leetcode 226)

2.4.2 对称二叉树 (Leetcode 101)

2.4.3 二叉树的最大深度(Leetcode 104)

2.4.4 二叉树的最小深度 (LeetCode 111)

2.4.5 完全二叉树的节点数

2.5 二叉搜索树

2.5.1 二叉搜索树的插入

2.5.2 二叉搜索树的删除节点

3.3 回溯法的模板：

3.4 对应的问题解决：

3.4.1 组合问题：

3.4.1.1 77.组合

3.4.1.2 216.组合总和 III

3.4.1.3 17.电话号码的字母组合

3.4.1.4 39.组合总和

3.4.1.5 40.组合总和 II

3.4.2 切割字符串问题

3.4.2.1 131. 分割回文串

3.4.2.2 93.复原 IP 地址

3.4.3 子集问题：

3.4.3.1 78. 子集

3.4.3.2 90. 子集 II

3.4.3.3 491.非递减子序列

8.1. `erase()`：精准外科手术（核心删除方法）

8.2. `pop_back()`：末端快删（轻量级删除）

8.3. `remove()` + `erase()`：批量删除的黄金组合

9. `string_view` (C++17 引入)：零拷贝的字符串“放大镜”

10. `join` 思想：告别低效的循环拼接