leetcode 写题的笔记

编码问题记录

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

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

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

1. 简化 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});

LeetCode笔记

1. 队列与栈

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

题目介绍

题目描述

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

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

示例:

示例 1：
输入：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

示例 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：

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

示例 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);

2. 返回值：

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

   所以终止条件是

   if(cur == nullptr){
   	return
   }

3. 确定单层递归的逻辑：

// 我们要实现中左右，而当前节点是中（要处理的目标），所以需要对中进行操作逻辑
//  处理中间节点，当前节点需要处理，所以直接走处理逻辑
		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)

题目链接

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

1. 我们可以发现，之前我们处理的方案，都是优先去访问中节点，拿到中节点的结果（无论中节点该在前还是在后），这就代表，最起码我们当前访问的节点的数据，当前必然能遇到

2. 但是中序遍历她不一样，她第一个访问的必定是最左下角的元素，即使倒置，第一个访问的也是最右下角的元素，这个元素和我们的根节点是没有关系的

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

   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 后序遍历如果不借助前序遍历倒置的话，该怎么做？（小拓展）

是啊，该怎么做？

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

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

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

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

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

1. 对于一个节点A，检查右节点B，如果没有，就优先处理右边

2. 右边的节点B处理完后（即右边的左右孩子都已得到处理）再处理节点A

3. 对于一个节点A，检查右节点B，如果没有，就优先处理右边

4. 右边的节点B处理完后（即右边的左右孩子都已得到处理）再处理栈里拿出来的节点A

5. ………….

   ---

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

   这时的逻辑就成了：

   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%计算量 ✅

---

💡 关键要点总结

💡 维护原则:

1. 何时选择 BFS:
   • 求最小深度、最短路径等”首次遇到即最优”的问题
   • 树的宽度远小于高度时(BFS队列开销小)
   • 需要按层级处理节点的场景
2. 何时选择 DFS:
   • 需要遍历所有节点或所有路径的问题
   • 树的高度较浅时(递归栈开销小)
   • 需要自底向上汇总信息的场景(如对称性判断)
3. 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^n$

节点数 = $2^h - 1 $

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

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