C++算法（树算法）
1. 二叉树的前序、中序、后序遍历
思路解析：
- 前序遍历（Pre-order）：根 -> 左 -> 右
- 中序遍历（In-order）：左 -> 根 -> 右
- 后序遍历（Post-order）：左 -> 右 -> 根
- 可以用递归或迭代（栈）实现
- 时间复杂度：O(N)，空间复杂度：O(H)，H 为树的高度
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// 二叉树节点定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// ========== 递归实现 ==========
// 前序遍历：根 -> 左 -> 右
void preorderRecursive(TreeNode* root, vector<int>& result) {
if (root == nullptr) return;
result.push_back(root->val); // 访问根节点
preorderRecursive(root->left, result); // 遍历左子树
preorderRecursive(root->right, result); // 遍历右子树
}
// 中序遍历：左 -> 根 -> 右
void inorderRecursive(TreeNode* root, vector<int>& result) {
if (root == nullptr) return;
inorderRecursive(root->left, result); // 遍历左子树
result.push_back(root->val); // 访问根节点
inorderRecursive(root->right, result); // 遍历右子树
}
// 后序遍历：左 -> 右 -> 根
void postorderRecursive(TreeNode* root, vector<int>& result) {
if (root == nullptr) return;
postorderRecursive(root->left, result); // 遍历左子树
postorderRecursive(root->right, result); // 遍历右子树
result.push_back(root->val); // 访问根节点
}
// ========== 迭代实现（使用栈）==========
// 前序遍历（迭代）
vector<int> preorderIterative(TreeNode* root) {
vector<int> result;
if (root == nullptr) return result;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
// 先压右子树，再压左子树（栈是后进先出）
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
return result;
}
// 中序遍历（迭代）
vector<int> inorderIterative(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* curr = root;
while (curr != nullptr || !st.empty()) {
// 一直往左走，将所有左节点入栈
while (curr != nullptr) {
st.push(curr);
curr = curr->left;
}
// 访问栈顶节点
curr = st.top();
st.pop();
result.push_back(curr->val);
// 转向右子树
curr = curr->right;
}
return result;
}
// 后序遍历（迭代）
vector<int> postorderIterative(TreeNode* root) {
vector<int> result;
if (root == nullptr) return result;
stack<TreeNode*> st1, st2;
st1.push(root);
// 使用两个栈，第一个栈按 根->右->左 的顺序
// 第二个栈反转后就是 左->右->根
while (!st1.empty()) {
TreeNode* node = st1.top();
st1.pop();
st2.push(node);
if (node->left) st1.push(node->left);
if (node->right) st1.push(node->right);
}
// 从第二个栈中取出结果
while (!st2.empty()) {
result.push_back(st2.top()->val);
st2.pop();
}
return result;
}
int main() {
// 构建测试树
// 1
// / \
// 2 3
// / \
// 4 5
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 递归遍历
vector<int> preorder, inorder, postorder;
preorderRecursive(root, preorder);
inorderRecursive(root, inorder);
postorderRecursive(root, postorder);
cout << "前序遍历（递归）: ";
for (int val : preorder) cout << val << " ";
cout << endl;
cout << "中序遍历（递归）: ";
for (int val : inorder) cout << val << " ";
cout << endl;
cout << "后序遍历（递归）: ";
for (int val : postorder) cout << val << " ";
cout << endl;
// 迭代遍历
cout << "\n前序遍历（迭代）: ";
vector<int> preorderIter = preorderIterative(root);
for (int val : preorderIter) cout << val << " ";
cout << endl;
cout << "中序遍历（迭代）: ";
vector<int> inorderIter = inorderIterative(root);
for (int val : inorderIter) cout << val << " ";
cout << endl;
cout << "后序遍历（迭代）: ";
vector<int> postorderIter = postorderIterative(root);
for (int val : postorderIter) cout << val << " ";
cout << endl;
return 0;
}
2. 判断一个二叉树是否是平衡二叉树
思路解析：
- 平衡二叉树：每个节点的左右子树高度差不超过 1
- 递归判断：对于每个节点，检查左右子树是否平衡，且高度差 ≤ 1
- 优化：在计算高度的同时判断是否平衡，避免重复计算
- 时间复杂度：O(N)
#include <iostream>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 辅助函数：计算高度并判断是否平衡
// 返回 -1 表示不平衡，否则返回高度
int checkHeight(TreeNode* root) {
if (root == nullptr) return 0; // 空树高度为 0
// 递归检查左子树
int leftHeight = checkHeight(root->left);
if (leftHeight == -1) return -1; // 左子树不平衡
// 递归检查右子树
int rightHeight = checkHeight(root->right);
if (rightHeight == -1) return -1; // 右子树不平衡
// 检查当前节点的左右子树高度差
if (abs(leftHeight - rightHeight) > 1) {
return -1; // 高度差超过 1，不平衡
}
// 返回当前节点的高度
return max(leftHeight, rightHeight) + 1;
}
// 判断是否为平衡二叉树
bool isBalanced(TreeNode* root) {
return checkHeight(root) != -1;
}
int main() {
// 测试 1：平衡二叉树
// 1
// / \
// 2 3
// / \
// 4 5
TreeNode* root1 = new TreeNode(1);
root1->left = new TreeNode(2);
root1->right = new TreeNode(3);
root1->left->left = new TreeNode(4);
root1->left->right = new TreeNode(5);
cout << "测试 1: " << (isBalanced(root1) ? "是平衡二叉树" : "不是平衡二叉树") << endl;
// 测试 2：不平衡二叉树
// 1
// /
// 2
// /
// 3
TreeNode* root2 = new TreeNode(1);
root2->left = new TreeNode(2);
root2->left->left = new TreeNode(3);
cout << "测试 2: " << (isBalanced(root2) ? "是平衡二叉树" : "不是平衡二叉树") << endl;
return 0;
}
3. 二叉树的最大深度
思路解析：
- 最大深度：从根节点到最远叶子节点的最长路径上的节点数
- 递归：最大深度 = max(左子树深度, 右子树深度) + 1
- 时间复杂度：O(N)
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// ========== 递归实现 ==========
int maxDepthRecursive(TreeNode* root) {
if (root == nullptr) return 0; // 空树深度为 0
// 递归计算左右子树的最大深度
int leftDepth = maxDepthRecursive(root->left);
int rightDepth = maxDepthRecursive(root->right);
// 返回较大的深度 + 1（当前节点）
return max(leftDepth, rightDepth) + 1;
}
// ========== 迭代实现（层次遍历）==========
int maxDepthIterative(TreeNode* root) {
if (root == nullptr) return 0;
queue<TreeNode*> q;
q.push(root);
int depth = 0;
while (!q.empty()) {
int levelSize = q.size(); // 当前层的节点数
depth++; // 深度加 1
// 遍历当前层的所有节点
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return depth;
}
int main() {
// 构建测试树
// 3
// / \
// 9 20
// / \
// 15 7
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
cout << "最大深度（递归）: " << maxDepthRecursive(root) << endl;
cout << "最大深度（迭代）: " << maxDepthIterative(root) << endl;
return 0;
}
4. 二叉树的最小深度
思路解析：
- 最小深度：从根节点到最近叶子节点的最短路径上的节点数
- 注意：叶子节点是指没有子节点的节点
- 递归时需要特别处理只有一个子树的情况
- 时间复杂度：O(N)
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// ========== 递归实现 ==========
int minDepthRecursive(TreeNode* root) {
if (root == nullptr) return 0;
// 如果左子树为空，只计算右子树
if (root->left == nullptr) {
return minDepthRecursive(root->right) + 1;
}
// 如果右子树为空，只计算左子树
if (root->right == nullptr) {
return minDepthRecursive(root->left) + 1;
}
// 左右子树都存在，取较小的深度
int leftDepth = minDepthRecursive(root->left);
int rightDepth = minDepthRecursive(root->right);
return min(leftDepth, rightDepth) + 1;
}
// ========== 迭代实现（BFS 层次遍历）==========
int minDepthIterative(TreeNode* root) {
if (root == nullptr) return 0;
queue<TreeNode*> q;
q.push(root);
int depth = 1;
while (!q.empty()) {
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) q.push(node->left);
if (node->right) q.push(node->right);
}
depth++;
}
return depth;
}
int main() {
// 测试树
// 3
// / \
// 9 20
// / \
// 15 7
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
cout << "最小深度（递归）: " << minDepthRecursive(root) << endl;
cout << "最小深度（迭代）: " << minDepthIterative(root) << endl;
return 0;
}
5. 二叉树的层次遍历
思路解析：
- 层次遍历（Level Order Traversal）：按层从上到下、从左到右访问节点
- 使用队列（BFS）实现
- 可以返回每一层的节点值
- 时间复杂度：O(N)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 层次遍历，返回每一层的节点值
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (root == nullptr) return result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size(); // 当前层的节点数
vector<int> currentLevel; // 存储当前层的节点值
// 遍历当前层的所有节点
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
currentLevel.push_back(node->val);
// 将下一层的节点加入队列
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(currentLevel);
}
return result;
}
// 之字形层次遍历（Zigzag Level Order）
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
if (root == nullptr) return result;
queue<TreeNode*> q;
q.push(root);
bool leftToRight = true; // 标记遍历方向
while (!q.empty()) {
int levelSize = q.size();
vector<int> currentLevel(levelSize);
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
// 根据方向决定插入位置
int index = leftToRight ? i : (levelSize - 1 - i);
currentLevel[index] = node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(currentLevel);
leftToRight = !leftToRight; // 切换方向
}
return result;
}
int main() {
// 构建测试树
// 3
// / \
// 9 20
// / \
// 15 7
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
// 普通层次遍历
cout << "层次遍历:" << endl;
vector<vector<int>> levels = levelOrder(root);
for (auto& level : levels) {
for (int val : level) {
cout << val << " ";
}
cout << endl;
}
// 之字形层次遍历
cout << "\n之字形层次遍历:" << endl;
vector<vector<int>> zigzag = zigzagLevelOrder(root);
for (auto& level : zigzag) {
for (int val : level) {
cout << val << " ";
}
cout << endl;
}
return 0;
}
6. 将二叉树转换为链表（Flatten Binary Tree to Linked List）
思路解析：
- 将二叉树展开为单链表，按前序遍历的顺序
- 要求原地修改，使用 O(1) 额外空间
- 方法：递归处理右子树和左子树，将左子树插入到根节点和右子树之间
- 时间复杂度：O(N)
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// ========== 方法 1：递归实现 ==========
void flatten(TreeNode* root) {
if (root == nullptr) return;
// 递归展开左右子树
flatten(root->left);
flatten(root->right);
// 保存右子树
TreeNode* rightSubtree = root->right;
// 将左子树移到右边
root->right = root->left;
root->left = nullptr;
// 找到当前右子树的末尾
TreeNode* curr = root;
while (curr->right != nullptr) {
curr = curr->right;
}
// 将原来的右子树接到末尾
curr->right = rightSubtree;
}
// ========== 方法 2：迭代实现（Morris 遍历思想）==========
void flattenIterative(TreeNode* root) {
TreeNode* curr = root;
while (curr != nullptr) {
if (curr->left != nullptr) {
// 找到左子树的最右节点
TreeNode* rightmost = curr->left;
while (rightmost->right != nullptr) {
rightmost = rightmost->right;
}
// 将右子树接到左子树的最右节点
rightmost->right = curr->right;
// 将左子树移到右边
curr->right = curr->left;
curr->left = nullptr;
}
// 移动到下一个节点
curr = curr->right;
}
}
// 辅助函数：打印链表
void printList(TreeNode* root) {
while (root != nullptr) {
cout << root->val << " -> ";
root = root->right;
}
cout << "NULL" << endl;
}
int main() {
// 构建测试树
// 1
// / \
// 2 5
// / \ \
// 3 4 6
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(5);
root->left->left = new TreeNode(3);
root->left->right = new TreeNode(4);
root->right->right = new TreeNode(6);
flatten(root);
cout << "展开后的链表: ";
printList(root);
return 0;
}
7. 判断一个二叉树是否为二叉搜索树（BST）
思路解析：
- 二叉搜索树（BST）：左子树所有节点 < 根节点 < 右子树所有节点
- 递归判断：对于每个节点，检查其值是否在合法范围内
- 使用上下界限制节点值的范围
- 时间复杂度：O(N)
#include <iostream>
#include <climits>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// ========== 方法 1：递归 + 范围检查 ==========
bool isValidBSTHelper(TreeNode* root, long long minVal, long long maxVal) {
if (root == nullptr) return true;
// 检查当前节点的值是否在合法范围内
if (root->val <= minVal || root->val >= maxVal) {
return false;
}
// 递归检查左右子树
// 左子树的值必须在 (minVal, root->val) 范围内
// 右子树的值必须在 (root->val, maxVal) 范围内
return isValidBSTHelper(root->left, minVal, root->val) &&
isValidBSTHelper(root->right, root->val, maxVal);
}
bool isValidBST(TreeNode* root) {
return isValidBSTHelper(root, LLONG_MIN, LLONG_MAX);
}
// ========== 方法 2：中序遍历检查 ==========
// BST 的中序遍历结果应该是严格递增的
bool isValidBSTInorder(TreeNode* root) {
TreeNode* prev = nullptr; // 记录前一个访问的节点
// 辅助函数：中序遍历
function<bool(TreeNode*)> inorder = [&](TreeNode* node) -> bool {
if (node == nullptr) return true;
// 遍历左子树
if (!inorder(node->left)) return false;
// 检查当前节点
if (prev != nullptr && node->val <= prev->val) {
return false; // 不是严格递增
}
prev = node;
// 遍历右子树
return inorder(node->right);
};
return inorder(root);
}
int main() {
// 测试 1：有效的 BST
// 2
// / \
// 1 3
TreeNode* root1 = new TreeNode(2);
root1->left = new TreeNode(1);
root1->right = new TreeNode(3);
cout << "测试 1: " << (isValidBST(root1) ? "是 BST" : "不是 BST") << endl;
// 测试 2：无效的 BST
// 5
// / \
// 1 4
// / \
// 3 6
TreeNode* root2 = new TreeNode(5);
root2->left = new TreeNode(1);
root2->right = new TreeNode(4);
root2->right->left = new TreeNode(3);
root2->right->right = new TreeNode(6);
cout << "测试 2: " << (isValidBST(root2) ? "是 BST" : "不是 BST") << endl;
return 0;
}
8. 二叉搜索树的第 k 大元素
思路解析：
- BST 的中序遍历是升序序列
- 第 k 大元素 = 中序遍历的倒数第 k 个元素
- 可以反向中序遍历（右 -> 根 -> 左），得到降序序列
- 时间复杂度：O(N)，最坏情况；O(H + k)，平均情况
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// ========== 方法 1：反向中序遍历（右 -> 根 -> 左）==========
int kthLargest(TreeNode* root, int k) {
int count = 0; // 计数器
int result = -1;
// 辅助函数：反向中序遍历
function<void(TreeNode*)> reverseInorder = [&](TreeNode* node) {
if (node == nullptr || count >= k) return;
// 先遍历右子树（较大的值）
reverseInorder(node->right);
// 访问当前节点
count++;
if (count == k) {
result = node->val;
return;
}
// 再遍历左子树（较小的值）
reverseInorder(node->left);
};
reverseInorder(root);
return result;
}
// ========== 方法 2：正向中序遍历，找第 n-k+1 小的元素 ==========
int kthLargestAlternative(TreeNode* root, int k) {
// 先计算节点总数
function<int(TreeNode*)> countNodes = [&](TreeNode* node) -> int {
if (node == nullptr) return 0;
return 1 + countNodes(node->left) + countNodes(node->right);
};
int n = countNodes(root);
int target = n - k + 1; // 第 k 大 = 第 n-k+1 小
int count = 0;
int result = -1;
// 正向中序遍历
function<void(TreeNode*)> inorder = [&](TreeNode* node) {
if (node == nullptr || count >= target) return;
inorder(node->left);
count++;
if (count == target) {
result = node->val;
return;
}
inorder(node->right);
};
inorder(root);
return result;
}
int main() {
// 构建 BST
// 5
// / \
// 3 6
// / \
// 2 4
// /
// 1
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(3);
root->right = new TreeNode(6);
root->left->left = new TreeNode(2);
root->left->right = new TreeNode(4);
root->left->left->left = new TreeNode(1);
// 中序遍历：1, 2, 3, 4, 5, 6
// 第 1 大：6，第 2 大：5，第 3 大：4
cout << "第 1 大元素: " << kthLargest(root, 1) << endl;
cout << "第 2 大元素: " << kthLargest(root, 2) << endl;
cout << "第 3 大元素: " << kthLargest(root, 3) << endl;
return 0;
}
9. 从前序和中序遍历构造二叉树
思路解析：
- 前序遍历：根 -> 左 -> 右，第一个元素是根节点
- 中序遍历：左 -> 根 -> 右，根节点将序列分为左右子树
- 递归构造： 从前序遍历找到根节点在中序遍历中找到根节点位置，划分左右子树递归构造左右子树
- 使用哈希表优化中序遍历中根节点的查找
- 时间复杂度：O(N)
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 从前序和中序遍历构造二叉树
TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd,
vector<int>& inorder, int inStart, int inEnd,
unordered_map<int, int>& inorderMap) {
if (preStart > preEnd || inStart > inEnd) {
return nullptr;
}
// 前序遍历的第一个元素是根节点
int rootVal = preorder[preStart];
TreeNode* root = new TreeNode(rootVal);
// 在中序遍历中找到根节点的位置
int rootIndex = inorderMap[rootVal];
// 计算左子树的节点数量
int leftSize = rootIndex - inStart;
// 递归构造左子树
// 前序：[preStart+1, preStart+leftSize]
// 中序：[inStart, rootIndex-1]
root->left = buildTreeHelper(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, rootIndex - 1, inorderMap);
// 递归构造右子树
// 前序：[preStart+leftSize+1, preEnd]
// 中序：[rootIndex+1, inEnd]
root->right = buildTreeHelper(preorder, preStart + leftSize + 1, preEnd,
inorder, rootIndex + 1, inEnd, inorderMap);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// 构建中序遍历的值到索引的映射，便于快速查找
unordered_map<int, int> inorderMap;
for (int i = 0; i < inorder.size(); i++) {
inorderMap[inorder[i]] = i;
}
return buildTreeHelper(preorder, 0, preorder.size() - 1,
inorder, 0, inorder.size() - 1, inorderMap);
}
// 辅助函数：打印中序遍历（验证结果）
void printInorder(TreeNode* root) {
if (root == nullptr) return;
printInorder(root->left);
cout << root->val << " ";
printInorder(root->right);
}
int main() {
// 示例：
// 前序遍历：[3, 9, 20, 15, 7]
// 中序遍历：[9, 3, 15, 20, 7]
// 构造的树：
// 3
// / \
// 9 20
// / \
// 15 7
vector<int> preorder = {3, 9, 20, 15, 7};
vector<int> inorder = {9, 3, 15, 20, 7};
TreeNode* root = buildTree(preorder, inorder);
cout << "构造的树的中序遍历: ";
printInorder(root);
cout << endl;
return 0;
}
10. 从后序和中序遍历构造二叉树
思路解析：
- 后序遍历：左 -> 右 -> 根，最后一个元素是根节点
- 中序遍历：左 -> 根 -> 右，根节点将序列分为左右子树
- 递归构造： 从后序遍历找到根节点（最后一个元素）在中序遍历中找到根节点位置，划分左右子树递归构造左右子树
- 时间复杂度：O(N)
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 从后序和中序遍历构造二叉树
TreeNode* buildTreeHelper(vector<int>& postorder, int postStart, int postEnd,
vector<int>& inorder, int inStart, int inEnd,
unordered_map<int, int>& inorderMap) {
if (postStart > postEnd || inStart > inEnd) {
return nullptr;
}
// 后序遍历的最后一个元素是根节点
int rootVal = postorder[postEnd];
TreeNode* root = new TreeNode(rootVal);
// 在中序遍历中找到根节点的位置
int rootIndex = inorderMap[rootVal];
// 计算左子树的节点数量
int leftSize = rootIndex - inStart;
// 递归构造左子树
// 后序：[postStart, postStart+leftSize-1]
// 中序：[inStart, rootIndex-1]
root->left = buildTreeHelper(postorder, postStart, postStart + leftSize - 1,
inorder, inStart, rootIndex - 1, inorderMap);
// 递归构造右子树
// 后序：[postStart+leftSize, postEnd-1]
// 中序：[rootIndex+1, inEnd]
root->right = buildTreeHelper(postorder, postStart + leftSize, postEnd - 1,
inorder, rootIndex + 1, inEnd, inorderMap);
return root;
}
TreeNode* buildTreeFromPostIn(vector<int>& postorder, vector<int>& inorder) {
// 构建中序遍历的值到索引的映射
unordered_map<int, int> inorderMap;
for (int i = 0; i < inorder.size(); i++) {
inorderMap[inorder[i]] = i;
}
return buildTreeHelper(postorder, 0, postorder.size() - 1,
inorder, 0, inorder.size() - 1, inorderMap);
}
// 辅助函数：打印后序遍历（验证结果）
void printPostorder(TreeNode* root) {
if (root == nullptr) return;
printPostorder(root->left);
printPostorder(root->right);
cout << root->val << " ";
}
int main() {
// 示例：
// 后序遍历：[9, 15, 7, 20, 3]
// 中序遍历：[9, 3, 15, 20, 7]
// 构造的树：
// 3
// / \
// 9 20
// / \
// 15 7
vector<int> postorder = {9, 15, 7, 20, 3};
vector<int> inorder = {9, 3, 15, 20, 7};
TreeNode* root = buildTreeFromPostIn(postorder, inorder);
cout << "构造的树的后序遍历: ";
printPostorder(root);
cout << endl;
return 0;
}
11. 二叉树的最大路径和
思路解析：
- 路径：从任意节点到任意节点的序列（不一定经过根节点）
- 路径和：路径上所有节点值的总和
- 递归思路： 对于每个节点，计算经过该节点的最大路径和最大路径和 = 左子树最大贡献 + 右子树最大贡献 + 当前节点值返回给父节点的贡献 = max(左子树贡献, 右子树贡献) + 当前节点值
- 需要处理负数节点（可以选择不包含某个子树）
- 时间复杂度：O(N)
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
private:
int maxSum; // 记录全局最大路径和
// 计算以当前节点为起点的最大路径贡献
int maxGain(TreeNode* node) {
if (node == nullptr) return 0;
// 递归计算左右子树的最大贡献
// 如果贡献为负，则不选择该子树（取 0）
int leftGain = max(maxGain(node->left), 0);
int rightGain = max(maxGain(node->right), 0);
// 计算经过当前节点的最大路径和
int currentPathSum = node->val + leftGain + rightGain;
// 更新全局最大路径和
maxSum = max(maxSum, currentPathSum);
// 返回当前节点能提供给父节点的最大贡献
// 只能选择左或右其中一条路径
return node->val + max(leftGain, rightGain);
}
public:
int maxPathSum(TreeNode* root) {
maxSum = INT_MIN; // 初始化为最小值
maxGain(root);
return maxSum;
}
};
int main() {
// 测试 1：
// 1
// / \
// 2 3
// 最大路径和：2 + 1 + 3 = 6
TreeNode* root1 = new TreeNode(1);
root1->left = new TreeNode(2);
root1->right = new TreeNode(3);
Solution sol1;
cout << "测试 1 最大路径和: " << sol1.maxPathSum(root1) << endl;
// 测试 2：
// -10
// / \
// 9 20
// / \
// 15 7
// 最大路径和：15 + 20 + 7 = 42
TreeNode* root2 = new TreeNode(-10);
root2->left = new TreeNode(9);
root2->right = new TreeNode(20);
root2->right->left = new TreeNode(15);
root2->right->right = new TreeNode(7);
Solution sol2;
cout << "测试 2 最大路径和: " << sol2.maxPathSum(root2) << endl;
// 测试 3：包含负数
// -3
TreeNode* root3 = new TreeNode(-3);
Solution sol3;
cout << "测试 3 最大路径和: " << sol3.maxPathSum(root3) << endl;
return 0;
}
12. 二叉树的镜像
思路解析：
- 镜像二叉树：将二叉树的左右子树交换
- 递归实现：交换当前节点的左右子树，然后递归处理左右子树
- 迭代实现：使用队列或栈，逐层交换节点的左右子树
- 时间复杂度：O(N)
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// ========== 方法 1：递归实现 ==========
TreeNode* mirrorTree(TreeNode* root) {
if (root == nullptr) return nullptr;
// 交换左右子树
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
// 递归处理左右子树
mirrorTree(root->left);
mirrorTree(root->right);
return root;
}
// ========== 方法 2：迭代实现（使用队列）==========
TreeNode* mirrorTreeIterative(TreeNode* root) {
if (root == nullptr) return nullptr;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
// 交换当前节点的左右子树
TreeNode* temp = node->left;
node->left = node->right;
node->right = temp;
// 将左右子节点加入队列
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return root;
}
// ========== 判断两棵树是否互为镜像 ==========
bool isSymmetric(TreeNode* left, TreeNode* right) {
// 两个节点都为空，是镜像
if (left == nullptr && right == nullptr) return true;
// 只有一个为空，不是镜像
if (left == nullptr || right == nullptr) return false;
// 值不相等，不是镜像
if (left->val != right->val) return false;
// 递归检查：左的左子树和右的右子树，左的右子树和右的左子树
return isSymmetric(left->left, right->right) &&
isSymmetric(left->right, right->left);
}
// 判断一棵树是否对称（镜像对称）
bool isSymmetricTree(TreeNode* root) {
if (root == nullptr) return true;
return isSymmetric(root->left, root->right);
}
// 辅助函数：层次遍历打印树
void printLevelOrder(TreeNode* root) {
if (root == nullptr) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
if (node) {
cout << node->val << " ";
q.push(node->left);
q.push(node->right);
} else {
cout << "null ";
}
}
cout << endl;
}
}
int main() {
// 构建测试树
// 4
// / \
// 2 7
// / \ / \
// 1 3 6 9
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);
cout << "原始树的层次遍历:" << endl;
printLevelOrder(root);
// 镜像翻转
mirrorTree(root);
cout << "\n镜像后的层次遍历:" << endl;
printLevelOrder(root);
// 镜像后：
// 4
// / \
// 7 2
// / \ / \
// 9 6 3 1
// 测试对称树
cout << "\n测试对称树:" << endl;
TreeNode* symRoot = new TreeNode(1);
symRoot->left = new TreeNode(2);
symRoot->right = new TreeNode(2);
symRoot->left->left = new TreeNode(3);
symRoot->left->right = new TreeNode(4);
symRoot->right->left = new TreeNode(4);
symRoot->right->right = new TreeNode(3);
cout << "是否对称: " << (isSymmetricTree(symRoot) ? "是" : "否") << endl;
return 0;
}
C++八股文全集 文章被收录于专栏
本专栏系统梳理C++技术面试核心考点，涵盖语言基础、面向对象、内存管理、STL容器、模板编程及经典算法。从引用指针、虚函数表、智能指针等底层原理，到继承多态、运算符重载等OOP特性从const、static、inline等关键字辨析，到动态规划、KMP算法、并查集等手写实现。每个知识点以面试答题形式呈现，注重原理阐述而非冗长代码，帮助你快速构建完整知识体系，从容应对面试官提问，顺利拿下offer。
