LeetCode 226从翻转二叉树到 C++ 树/图/队列/栈实战：递归、BFS、DFS 三种解法全解析

一、引子：为什么一道"简单题"值得细讲？

LeetCode 226. 翻转二叉树，题目本身很短：

给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。

但它是理解树结构、递归、BFS、DFS 的最佳入口。很多初学者卡住的不是算法，而是：

• TreeNode* 到底怎么声明？

• new 和 delete 什么时候用？

• queue 和 stack 怎么用？

• 图又该怎么表示？

本文就把这道题作为载体，把树、图、队列、栈在 C++ 里的构建方式一次讲透。

二、树的基础：TreeNode 是怎么定义的？

2.1 LeetCode 的官方定义

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right)
: val(x), left(left), right(right) {}
};

关键点：

• left / right 是指针，指向子节点；空节点就是 nullptr。

• 三个构造函数让你可以灵活地创建：空节点、只有值的节点、带左右孩子的节点。

• 使用时通过 new 在堆上分配，例如：

TreeNode* root = new TreeNode(4);
root->left = new TreeNode(2);
root->right = new TreeNode(7);

2.2 手动构建示例 1 的那棵树

TreeNode* root = new TreeNode(4);
root->left = new TreeNode(2);
root->right = new TreeNode(7);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(3);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(9);

得到的就是题目里的：

2.3 用数组构建二叉树（层序）

竞赛里常给一个层序数组（如 [4,2,7,1,3,6,9]），表示 null 用 -1 或 nullopt。构建代码如下：

TreeNode* buildTree(const vector<int>& arr) {
if (arr.empty() || arr[0] == -1) return nullptr;
TreeNode* root = new TreeNode(arr[0]);
queue<TreeNode*> q;
q.push(root);
int i = 1;
while (!q.empty() && i < arr.size()) {
TreeNode* cur = q.front(); q.pop();
if (i < arr.size() && arr[i] != -1) {
cur->left = new TreeNode(arr[i]);
q.push(cur->left);
}
i++;
if (i < arr.size() && arr[i] != -1) {
cur->right = new TreeNode(arr[i]);
q.push(cur->right);
}
i++;
}
return root;
}

三、队列与栈：C++ STL 里的声明方式

3.1 queue（先进先出，FIFO）

#include <queue>
queue<TreeNode*> q; // 声明一个存放 TreeNode* 的队列
q.push(root); // 入队
q.front(); // 取队首
q.pop(); // 出队
q.empty(); // 判空
q.size(); // 大小

3.2 stack（后进先出，LIFO）

#include <stack>
stack<TreeNode*> stk; // 声明一个存放 TreeNode* 的栈
stk.push(root); // 入栈
stk.top(); // 取栈顶
stk.pop(); // 出栈
stk.empty(); // 判空
stk.size(); // 大小

3.3 记忆技巧

它们都是模板类，<> 里写元素类型——queue<int>、stack<TreeNode*>、vector<vector<int>> 等等。

四、解法一：递归（最简洁）

4.1 思路

对任意节点：

4.2 代码

class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return nullptr;

TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);

root->left = right;
root->right = left;
return root;
}
};

或者更紧凑：

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

4.3 执行过程

以 [4,2,7,1,3,6,9] 为例：

invertTree(4)
├─ invertTree(2)
│ ├─ invertTree(1) → 返回 1
│ ├─ invertTree(3) → 返回 3
│ └─ 交换 → 2.left = 3, 2.right = 1
├─ invertTree(7)
│ ├─ invertTree(6) → 返回 6
│ ├─ invertTree(9) → 返回 9
│ └─ 交换 → 7.left = 9, 7.right = 6
└─ 交换 → 4.left = 7, 4.right = 2

结果：[4,7,2,9,6,3,1] ✅

4.4 复杂度

• 时间 O(n)：每个节点访问一次。

• 空间 O(h)：函数调用栈，最坏（链状树）O(n)。

五、解法二：BFS（层序遍历 + 交换）

5.1 思路

用队列做层序遍历：每次取出一个节点，交换其左右孩子，再把非空孩子入队。所有节点处理完后，树就翻转过来了。

5.2 代码

class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return nullptr;

queue<TreeNode*> q;
q.push(root);

while (!q.empty()) {
TreeNode* node = q.front();
q.pop();

swap(node->left, node->right); // 交换

if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return root;
}
};

5.3 执行过程（BFS 顺序）

第 1 层：处理 4 → 交换 4 的左右 → 队列：[2, 7]
第 2 层：处理 2 → 交换 2 的左右 → 队列：[7, 1, 3]
处理 7 → 交换 7 的左右 → 队列：[1, 3, 6, 9]
第 3 层：1、3、6、9 都是叶子，交换无影响

结果一致。

5.4 复杂度

• 时间 O(n)：每个节点入队一次、出队一次。

• 空间 O(n)：队列最多存一层的节点数，最坏是 O(n)。

六、解法三：DFS（用栈模拟递归）

6.1 思路

递归本质是用系统栈，我们也可以自己用一个 stack 来模拟：

6.2 代码

class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return nullptr;

stack<TreeNode*> stk;
stk.push(root);

while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();

swap(node->left, node->right);

if (node->left) stk.push(node->left);
if (node->right) stk.push(node->right);
}
return root;
}
};

6.3 BFS 与 DFS 的差异

七、三种解法对比

面试首选递归，简洁、清晰。若面试官追问"不用递归怎么实现"，再给出 BFS 或 DFS 迭代。

八、图（Graph）在 C++ 中的构建

既然讲了树，顺势讲一下图。树是特殊的图（无环、连通），图的表示主要有两种：

8.1 邻接矩阵

适合稠密图，adj[i][j] = 1 表示 i → j 有边。

int n = 5;
vector<vector<int>> adj(n, vector<int>(n, 0));
adj[0][1] = 1;
adj[1][0] = 1; // 无向图对称

8.2 邻接表（最常用）

适合稀疏图，adj[i] 存所有与 i 相邻的点。

int n = 5;
vector<vector<int>> adj(n);

// 添加一条无向边 u-v
auto addEdge = [&](int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
};

addEdge(0, 1);
addEdge(1, 2);
addEdge(2, 3);

8.3 带权图

用 pair<int, int> 存 (邻居, 权值)：

vector<vector<pair<int,int>>> adj(n);
adj[u].push_back({v, w});
adj[v].push_back({u, w});

8.4 图的 DFS / BFS 模板

// 图 DFS
vector<bool> visited(n, false);
function<void(int)> dfs = [&](int u) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) dfs(v);
}
};
dfs(0);

// 图 BFS
queue<int> q;
vector<bool> vis(n, false);
q.push(0); vis[0] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}

树和图的区别：树无需 visited（没有环），图一般必须用 visited 防重复访问。

九、常见容器声明速查

// 数组
vector<int> a(n, 0); // 一维，n 个 0
vector<vector<int>> b(m, vector<int>(n)); // 二维，m 行 n 列

// 队列
queue<int> q;
queue<TreeNode*> qTree;

// 栈
stack<int> stk;
stack<TreeNode*> stkTree;

// 哈希表
unordered_map<int, int> mp;
unordered_set<int> st;

// 图（邻接表）
vector<vector<int>> adj(n);

// 优先队列（大根堆 / 小根堆）
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;

// 配对
pair<int, int> p = {1, 2};