二叉树
二叉树是算法竞赛中最常用的数据结构之一，它不仅是其他高级树形结构的基础，也是许多高效算法的核心组件。
基本概念
【定义】二叉树是一种树形结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。
二叉树的主要类型包括：
- 满二叉树：除叶节点外的所有节点都有两个子节点，且所有叶节点都在同一层
- 完全二叉树：除最后一层外，其他层的节点都是满的，且最后一层的节点都靠左排列
- 平衡二叉树：任意节点的左右子树高度差不超过1
- 二叉搜索树：左子树上所有节点的值都小于根节点，右子树上所有节点的值都大于根节点
二叉树的表示
链式表示
struct TreeNode {
int val; // 节点值
TreeNode *left; // 左子节点指针
TreeNode *right; // 右子节点指针
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
【链式表示分析】
- 优点：结构灵活，易于实现动态操作（插入、删除节点）
- 缺点：额外的指针开销，内存分散可能导致缓存不友好
- 适用场景：一般用于结构不规则的二叉树，如BST、平衡树等
- ACM中常见用法：大多数树题目都使用此表示方法，因为操作更为灵活
数组表示
对于完全二叉树，可以使用数组进行高效存储：
- 根节点存储在索引1（或0，取决于实现）
- 对于索引为i的节点，其左子节点的索引为2i，右子节点的索引为2i+1（如果索引从1开始）
const int MAXN = 1005;
int tree[MAXN]; // 使用数组存储完全二叉树
【数组表示分析】
- 优点：内存连续，访问迅速，无需存储指针
- 缺点：对非完全二叉树会浪费空间
- 适用场景：堆、线段树等完全二叉树结构
- ACM常见应用：
// 索引从1开始的完全二叉树操作示例 inline int left(int i) { return i << 1; } // 左子节点: 2*i inline int right(int i) { return (i << 1) | 1; } // 右子节点: 2*i+1 inline int parent(int i) { return i >> 1; } // 父节点: i/2 - 易错点：索引计算时的起始值(0或1)混淆会导致严重错误
二叉树的遍历
深度优先遍历
前序遍历 (根-左-右)
void preorder(TreeNode* root) {
if (root == nullptr) return;
cout << root->val << " "; // 访问根节点
preorder(root->left); // 遍历左子树
preorder(root->right); // 遍历右子树
}
// 非递归实现
vector<int> preorderIterative(TreeNode* root) {
vector<int> result;
if (root == nullptr) return result;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
result.push_back(node->val); // 访问节点
// 注意：先压入右子节点，再压入左子节点，这样出栈时会先处理左子节点
if (node->right) s.push(node->right);
if (node->left) s.push(node->left);
}
return result;
}
【前序遍历分析】
- 实现思路：先访问当前节点，再递归访问左右子树
- ACM应用场景：构建树的复制、序列化二叉树
- 递归vs迭代：递归代码简洁但有栈溢出风险；迭代需要手动管理栈但更安全
- 时间复杂度：O(n)，每个节点恰好被访问一次
- 空间复杂度：递归O(h)，迭代O(h)，h为树高，最坏情况O(n)
中序遍历 (左-根-右)
void inorder(TreeNode* root) {
if (root == nullptr) return;
inorder(root->left); // 遍历左子树
cout << root->val << " "; // 访问根节点
inorder(root->right); // 遍历右子树
}
// 非递归实现
vector<int> inorderIterative(TreeNode* root) {
vector<int> result;
stack<TreeNode*> s;
TreeNode* curr = root;
while (curr != nullptr || !s.empty()) {
// 一直向左遍历，将所有节点入栈
while (curr != nullptr) {
s.push(curr);
curr = curr->left;
}
// 弹出栈顶节点并访问
curr = s.top();
s.pop();
result.push_back(curr->val);
// 转向右子树
curr = curr->right;
}
return result;
}
【中序遍历分析】
- 实现思路：递归或迭代方式按"左-根-右"顺序访问节点
- ACM应用特点：对BST进行中序遍历可以得到有序序列，常用于判断BST合法性
- 易错点：迭代版本的双重循环逻辑较复杂，要注意内外循环的结束条件
- 优化思路：可使用Morris遍历降低空间复杂度至O(1)
- 测试用例设计：
- 单节点树：检验基本功能
- 链状树（只有左子树或只有右子树）：测试极端情况
- 满二叉树：测试平衡情况
后序遍历 (左-右-根)
void postorder(TreeNode* root) {
if (root == nullptr) return;
postorder(root->left); // 遍历左子树
postorder(root->right); // 遍历右子树
cout << root->val << " "; // 访问根节点
}
// 非递归实现
vector<int> postorderIterative(TreeNode* root) {
vector<int> result;
if (root == nullptr) return result;
stack<TreeNode*> s1, s2;
s1.push(root);
// 第一次遍历，将节点按根-右-左的顺序压入 s2
while (!s1.empty()) {
TreeNode* node = s1.top();
s1.pop();
s2.push(node);
if (node->left) s1.push(node->left);
if (node->right) s1.push(node->right);
}
// 从 s2 中弹出节点，顺序即为左-右-根
while (!s2.empty()) {
result.push_back(s2.top()->val);
s2.pop();
}
return result;
}
【后序遍历分析】
- 实现思路：使用双栈法是非递归实现中最直观的方式
- ACM应用场景：树的删除操作、表达式计算树求值
- 复杂度优化：双栈法空间复杂度为O(n)，但实现简单易懂
- 单栈实现提示：需要记录上一个访问的节点，判断右子树是否已访问，实现更复杂
- 易错点：直接修改前序遍历代码（调整左右子树压栈顺序，再反转结果）不足以实现后序遍历
广度优先遍历 (层序遍历)
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;
}
【层序遍历分析】
- 算法思路：使用队列按层从上到下遍历节点
- 数据结构：必须使用队列(FIFO)，不能用栈
- 标准实现：通过记录当前层的节点数量来分离不同层的节点
- ACM实战应用：
- 计算二叉树的宽度
- 寻找最近公共祖先
- 判断是否为完全二叉树
实现变种：
// 简化版层序遍历(仅输出值) void simpleLevelOrder(TreeNode* root) { if (!root) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* node = q.front(); q.pop(); cout << node->val << " "; // 访问节点 if (node->left) q.push(node->left); if (node->right) q.push(node->right); } }- 时间复杂度：O(n)
- 空间复杂度：O(w)，其中w是树的最大宽度，最坏情况O(n/2)≈O(n)
二叉树的构造
从前序和中序遍历构造二叉树
/**
* 根据前序遍历和中序遍历序列构造二叉树
* 前序遍历的第一个元素是根节点，中序遍历中根节点左侧是左子树，右侧是右子树
* @param preorder 前序遍历序列 [根节点, [左子树的前序遍历], [右子树的前序遍历]]
* @param inorder 中序遍历序列 [[左子树的中序遍历], 根节点, [右子树的中序遍历]]
* @return 构造的二叉树根节点
*/
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTreeHelper(preorder, 0, preorder.size() - 1,
inorder, 0, inorder.size() - 1);
}
/**
* 递归辅助函数，用于构造二叉树的子树
* @param preorder 前序遍历序列
* @param preStart 当前子树在前序序列中的起始索引
* @param preEnd 当前子树在前序序列中的结束索引
* @param inorder 中序遍历序列
* @param inStart 当前子树在中序序列中的起始索引
* @param inEnd 当前子树在中序序列中的结束索引
* @return 当前子树的根节点
*/
TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd,
vector<int>& inorder, int inStart, int inEnd) {
// 递归终止条件：如果索引范围无效，返回空节点
if (preStart > preEnd || inStart > inEnd) return nullptr;
// 根节点是前序遍历的第一个节点
int rootVal = preorder[preStart];
TreeNode* root = new TreeNode(rootVal);
// 在中序遍历中找到根节点的位置
// 中序遍历中，根节点左侧的节点属于左子树，右侧的节点属于右子树
int rootIndex = inStart;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
// 计算左子树的节点数量
// 这个数量用于确定前序遍历中左子树的范围
int leftSubtreeSize = rootIndex - inStart;
// 递归构造左右子树
// 左子树：
// - 前序范围：[preStart+1, preStart+leftSubtreeSize]
// - 中序范围：[inStart, rootIndex-1]
root->left = buildTreeHelper(preorder, preStart + 1, preStart + leftSubtreeSize,
inorder, inStart, rootIndex - 1);
// 右子树：
// - 前序范围：[preStart+leftSubtreeSize+1, preEnd]
// - 中序范围：[rootIndex+1, inEnd]
root->right = buildTreeHelper(preorder, preStart + leftSubtreeSize + 1, preEnd,
inorder, rootIndex + 1, inEnd);
return root;
}
【构造二叉树分析】
算法原理：
- 前序遍历的第一个元素是根节点
- 在中序遍历中找到根节点位置，划分左右子树
- 递归构建左右子树
ACM常见题型：根据各种遍历序列重建二叉树
- 前序+中序 → 二叉树（经典题型）
- 后序+中序 → 二叉树
- 前序+后序 → 完全二叉树（解不唯一）
性能优化：
// 使用哈希表优化根节点查找 unordered_map<int, int> buildIndexMap(vector<int>& inorder) { unordered_map<int, int> map; for (int i = 0; i < inorder.size(); i++) { map[inorder[i]] = i; } return map; } // 优化的构建函数 TreeNode* buildTreeOptimized(vector<int>& preorder, vector<int>& inorder) { unordered_map<int, int> indexMap = buildIndexMap(inorder); return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, indexMap); } TreeNode* buildTreeHelper(..., unordered_map<int, int>& indexMap) { // 使用indexMap直接查找根节点位置，避免O(n)的线性查找 int rootIndex = indexMap[rootVal]; // 其他代码不变... }复杂度分析：
- 原始实现：时间O(n²)，每层递归中查找rootIndex需要O(n)
- 哈希表优化：时间O(n)，空间O(n)
易错点：
- 索引计算错误导致子树划分不正确
- 没有考虑到树中可能有重复值的情况
- 递归基础情况处理不当可能导致无限递归
从后序和中序遍历构造二叉树
/**
* 根据后序遍历和中序遍历序列构造二叉树
* 后序遍历的最后一个元素是根节点，中序遍历中根节点左侧是左子树，右侧是右子树
* @param postorder 后序遍历序列 [[左子树的后序遍历], [右子树的后序遍历], 根节点]
* @param inorder 中序遍历序列 [[左子树的中序遍历], 根节点, [右子树的中序遍历]]
* @return 构造的二叉树根节点
*/
TreeNode* buildFromPostAndIn(vector<int>& postorder, vector<int>& inorder) {
// 构建中序遍历值到索引的映射，用于快速查找根节点在中序遍历中的位置
unordered_map<int, int> indexMap;
for (int i = 0; i < inorder.size(); i++) {
indexMap[inorder[i]] = i;
}
return buildFromPostAndInHelper(postorder, 0, postorder.size() - 1,
inorder, 0, inorder.size() - 1, indexMap);
}
/**
* 递归辅助函数，用于构造二叉树的子树
* @param postorder 后序遍历序列
* @param postStart 当前子树在后序序列中的起始索引
* @param postEnd 当前子树在后序序列中的结束索引
* @param inorder 中序遍历序列
* @param inStart 当前子树在中序序列中的起始索引
* @param inEnd 当前子树在中序序列中的结束索引
* @param indexMap 中序遍历值到索引的映射表
* @return 当前子树的根节点
*/
TreeNode* buildFromPostAndInHelper(vector<int>& postorder, int postStart, int postEnd,
vector<int>& inorder, int inStart, int inEnd,
unordered_map<int, int>& indexMap) {
// 递归终止条件：如果索引范围无效，返回空节点
if (postStart > postEnd || inStart > inEnd) return nullptr;
// 后序遍历的最后一个元素是当前子树的根节点
int rootVal = postorder[postEnd];
TreeNode* root = new TreeNode(rootVal);
// 在中序遍历中找到根节点的位置 - 使用哈希表实现O(1)查找
int rootIndex = indexMap[rootVal];
// 计算左子树的节点数量
// 这个数量用于确定后序遍历中左子树的范围
int leftSubtreeSize = rootIndex - inStart;
// 递归构造左右子树
// 左子树：
// - 后序范围：[postStart, postStart+leftSubtreeSize-1]
// - 中序范围：[inStart, rootIndex-1]
root->left = buildFromPostAndInHelper(postorder, postStart, postStart + leftSubtreeSize - 1,
inorder, inStart, rootIndex - 1, indexMap);
// 右子树：
// - 后序范围：[postStart+leftSubtreeSize, postEnd-1]
// - 中序范围：[rootIndex+1, inEnd]
// 注意：后序遍历中，根节点在最后，其前面是右子树，再前面是左子树
root->right = buildFromPostAndInHelper(postorder, postStart + leftSubtreeSize, postEnd - 1,
inorder, rootIndex + 1, inEnd, indexMap);
return root;
}
【后序+中序构造分析】
- 算法原理：
- 后序遍历的最后一个元素是根节点
- 在中序遍历中找到根节点位置，划分左右子树
- 递归构建左右子树
- 实现难点：后序遍历中子树范围的计算较前序遍历更复杂
- 左子树：postStart ~ (postStart + leftSize - 1)
- 右子树：(postStart + leftSize) ~ (postEnd - 1)
- 优化策略：
- 使用哈希表存储中序遍历的值到索引的映射，将查找根节点位置的复杂度从O(n)降低到O(1)
- 直接传递子树大小而不是重新计算
- ACM应用场景：解析表达式树、处理语法分析树
- 易错点：
- 后序遍历的索引划分容易出错，注意右子树结束位置是postEnd-1
- 处理空树或只有一个节点的特殊情况
从层序遍历构造完全二叉树
/**
* 根据层序遍历序列构造完全二叉树
* 层序遍历按照从上到下、从左到右的顺序访问节点
* @param levelOrder 层序遍历序列 [根节点, 第二层节点..., 第n层节点...]
* @return 构造的二叉树根节点
*/
TreeNode* buildFromLevelOrder(vector<int>& levelOrder) {
// 空序列返回空树
if (levelOrder.empty()) return nullptr;
// 创建根节点
TreeNode* root = new TreeNode(levelOrder[0]);
queue<TreeNode*> q; // 使用队列按层构建树节点
q.push(root);
int i = 1; // 从第二个元素开始（索引1）
// 按照完全二叉树的性质，使用层序遍历构建树
while (!q.empty() && i < levelOrder.size()) {
// 获取当前要处理的父节点
TreeNode* current = q.front();
q.pop();
// 处理左子节点 (2*i)
if (i < levelOrder.size()) {
if (levelOrder[i] != -1) { // 假设-1表示空节点
// 创建左子节点并加入队列
current->left = new TreeNode(levelOrder[i]);
q.push(current->left);
}
i++; // 移动到下一个元素
// 处理右子节点 (2*i+1)
if (i < levelOrder.size()) {
if (levelOrder[i] != -1) { // 假设-1表示空节点
// 创建右子节点并加入队列
current->right = new TreeNode(levelOrder[i]);
q.push(current->right);
}
i++; // 移动到下一个元素
}
}
}
return root;
}
【层序构造分析】
算法原理：利用队列按层构建树节点
- 首先创建根节点（层序遍历的第一个元素）
- 使用队列跟踪当前层的节点
- 为队列中的每个节点分配其左右子节点（如果存在）
数据结构：
- 队列用于按层次顺序处理节点
- 层序遍历数组中的空节点通常使用特殊值（如-1或null）表示
时间复杂度：O(n)，每个节点只处理一次
空间复杂度：O(w)，其中w是树的最大宽度（最后一层的节点数），最坏情况下约为n/2
实现技巧：
- 使用索引i跟踪层序序列中的当前位置
- 对于每个父节点，先处理左子节点，再处理右子节点
- 确保索引不超出数组范围
适用场景：
- 从数组表示转换为链式表示的树结构
- 解析堆的数组表示并构建树形结构
- 生成完全二叉树进行可视化或分析
易错点：
- 忘记检查空节点标记
- 索引增量计算错误
- 未正确处理数组边界条件 ````
从字符串表示构造二叉树
处理括号表示法的二叉树字符串，如："1(2)(3(4)(5))"
TreeNode* buildFromBracketNotation(string s) {
if (s.empty()) return nullptr;
int i = 0;
return parseNode(s, i);
}
TreeNode* parseNode(const string& s, int& i) {
// 解析节点值
string num;
while (i < s.size() && s[i] >= '0' && s[i] <= '9') {
num += s[i++];
}
if (num.empty()) return nullptr;
TreeNode* node = new TreeNode(stoi(num));
// 解析左子树
if (i < s.size() && s[i] == '(') {
i++; // 跳过左括号
node->left = parseNode(s, i);
i++; // 跳过右括号
}
// 解析右子树
if (i < s.size() && s[i] == '(') {
i++; // 跳过左括号
node->right = parseNode(s, i);
i++; // 跳过右括号
}
return node;
}
【字符串构造分析】
- 算法原理：递归解析括号表示的树结构
- 实现技巧：使用引用传递索引位置，跟踪当前解析位置
- ACM应用：解析输入的树形结构字符串表示
- 注意事项：需处理多位数字、空节点和格式错误等边界情况
构造特殊的二叉树
构造平衡二叉搜索树
从排序数组构造平衡BST：
TreeNode* sortedArrayToBST(vector<int>& nums) {
return buildBST(nums, 0, nums.size() - 1);
}
TreeNode* buildBST(vector<int>& nums, int left, int right) {
if (left > right) return nullptr;
// 总是选择中间位置的元素作为根节点
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
// 递归构造左右子树
root->left = buildBST(nums, left, mid - 1);
root->right = buildBST(nums, mid + 1, right);
return root;
}
【构造平衡BST分析】
- 核心思想：始终选择数组中间元素作为子树根节点
- 时间复杂度：O(n)
- 特点：构造出的树高度最小，约为log(n)
- 应用场景：需要快速构建平衡搜索树的场景
构造线段树
// 线段树节点
struct SegmentTreeNode {
int start, end; // 区间范围
int sum; // 区间和（可根据需要改为其他聚合值）
SegmentTreeNode *left, *right;
SegmentTreeNode(int s, int e) : start(s), end(e), sum(0), left(nullptr), right(nullptr) {}
};
// 从数组构建线段树
SegmentTreeNode* buildSegmentTree(vector<int>& nums, int start, int end) {
if (start > end) return nullptr;
SegmentTreeNode* root = new SegmentTreeNode(start, end);
if (start == end) {
// 叶节点，代表单个元素
root->sum = nums[start];
} else {
int mid = start + (end - start) / 2;
root->left = buildSegmentTree(nums, start, mid);
root->right = buildSegmentTree(nums, mid + 1, end);
// 合并子节点信息
root->sum = (root->left ? root->left->sum : 0) +
(root->right ? root->right->sum : 0);
}
return root;
}
【线段树构造分析】
- 应用场景：区间查询和修改问题
- 构造思路：自顶向下分割区间，自底向上聚合信息
- 时间复杂度：O(n)
- ACM实战提示：线段树是解决区间问题的强大工具，掌握其构造和操作是算法竞赛的基本要求
二叉树的应用
二叉搜索树 (BST)
二叉搜索树是特殊的二叉树，它满足以下性质：
- 左子树上所有节点的值都小于根节点的值
- 右子树上所有节点的值都大于根节点的值
- 左右子树也都是二叉搜索树
BST的查找操作
TreeNode* search(TreeNode* root, int key) {
if (root == nullptr || root->val == key) return root;
if (key < root->val) {
return search(root->left, key); // 在左子树中查找
} else {
return search(root->right, key); // 在右子树中查找
}
}
// 非递归实现
TreeNode* searchIterative(TreeNode* root, int key) {
TreeNode* curr = root;
while (curr != nullptr && curr->val != key) {
if (key < curr->val) {
curr = curr->left;
} else {
curr = curr->right;
}
}
return curr; // 如果找不到，返回nullptr
}
【BST查找分析】
- 算法思路：利用BST的有序性质，通过比较节点值与目标值大小决定搜索方向
- 时间复杂度：平均O(log n)，最坏O(n)（当树退化为链表时）
- 递归与迭代：迭代版本避免了函数调用开销，更适合ACM比赛
- ACM实战应用：实现各种集合、映射操作
- 优化建议：对于不平衡的BST，考虑使用平衡树如AVL或红黑树
BST的插入操作
TreeNode* insert(TreeNode* root, int key) {
if (root == nullptr) return new TreeNode(key);
if (key < root->val) {
root->left = insert(root->left, key);
} else if (key > root->val) {
root->right = insert(root->right, key);
}
return root; // 返回更新后的树的根节点
}
// 非递归实现
TreeNode* insertIterative(TreeNode* root, int key) {
TreeNode* newNode = new TreeNode(key);
if (root == nullptr) return newNode;
TreeNode* curr = root;
TreeNode* parent = nullptr;
while (curr != nullptr) {
parent = curr;
if (key < curr->val) {
curr = curr->left;
} else if (key > curr->val) {
curr = curr->right;
} else {
// 键已存在，不进行插入
delete newNode;
return root;
}
}
// 确定新节点是父节点的左子节点还是右子节点
if (key < parent->val) {
parent->left = newNode;
} else {
parent->right = newNode;
}
return root;
}
【BST插入分析】
- 算法原理：通过比较寻找合适的插入位置
- 关键点：BST不允许重复值（标准定义下），需要特殊处理
- 时间复杂度：平均O(log n)，最坏O(n)
- ACM应用：动态维护有序数据集合，multiset实现
- 易错点：
- 插入操作可能改变根节点，需要正确处理返回值
- 不正确处理树中已存在的重复值会导致内存泄漏
- 迭代版本必须记录parent节点才能连接新节点
BST的删除操作
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return nullptr;
// 寻找要删除的节点
if (key < root->val) {
root->left = deleteNode(root->left, key);
} else if (key > root->val) {
root->right = deleteNode(root->right, key);
} else {
// 找到要删除的节点
// 情况1: 叶节点（无子节点）
if (root->left == nullptr && root->right == nullptr) {
delete root;
return nullptr;
}
// 情况2: 只有一个子节点
else if (root->left == nullptr) {
TreeNode* temp = root->right;
delete root;
return temp;
}
else if (root->right == nullptr) {
TreeNode* temp = root->left;
delete root;
return temp;
}
// 情况3: 有两个子节点
else {
// 找到右子树中的最小节点（或左子树中的最大节点）
TreeNode* temp = findMin(root->right);
// 用该节点的值替换当前节点的值
root->val = temp->val;
// 删除右子树中的最小节点
root->right = deleteNode(root->right, temp->val);
}
}
return root;
}
TreeNode* findMin(TreeNode* node) {
while (node->left != nullptr) {
node = node->left;
}
return node;
}
【BST删除分析】
算法思路：分三种情况处理删除操作
- 叶节点：直接删除
- 有一个子节点：用子节点替换
- 有两个子节点：用后继节点（或前驱节点）替换，再删除后继
复杂度分析：
- 时间复杂度：平均O(log n)，最坏O(n)
- 空间复杂度：递归实现O(h)，h为树高
ACM实战技巧：
- 题目中如果只需要考虑插入和查找操作，可省略删除操作，简化代码
- 删除是BST中最复杂的操作，实现时考虑用标记删除（懒删除）简化
常见错误：
- 忘记释放被删除节点的内存
- 处理有两个子节点的情况时，没有正确递归删除替换节点
- 对根节点的改变处理不当
二叉树的常见操作
计算二叉树的高度
int height(TreeNode* root) {
if (root == nullptr) return 0;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return max(leftHeight, rightHeight) + 1;
}
检查二叉树是否平衡
bool isBalanced(TreeNode* root) {
return checkHeight(root) != -1;
}
// 返回树的高度，如果不平衡则返回-1
int checkHeight(TreeNode* root) {
if (root == nullptr) return 0;
int leftHeight = checkHeight(root->left);
if (leftHeight == -1) return -1;
int rightHeight = checkHeight(root->right);
if (rightHeight == -1) return -1;
// 检查高度差是否超过1
if (abs(leftHeight - rightHeight) > 1) return -1;
return max(leftHeight, rightHeight) + 1;
}
【平衡检查分析】
- 算法原理：自底向上检查每个节点的左右子树高度差
- 优化思路：使用一个函数同时计算高度和判断平衡性，避免重复计算
- 时间复杂度：O(n)，每个节点只访问一次
对比分析：
// 朴素解法（低效）- O(n²) bool isBalancedNaive(TreeNode* root) { if (root == nullptr) return true; int leftHeight = height(root->left); int rightHeight = height(root->right); return abs(leftHeight - rightHeight) <= 1 && isBalancedNaive(root->left) && isBalancedNaive(root->right); }- ACM应用：AVL树相关问题，验证树的合法性
二叉树的序列化与反序列化
// 序列化二叉树
string serialize(TreeNode* root) {
if (root == nullptr) return "X,"; // 使用X表示空节点
string result = to_string(root->val) + ",";
result += serialize(root->left);
result += serialize(root->right);
return result;
}
// 反序列化二叉树
TreeNode* deserialize(string data) {
queue<string> nodes;
string val;
// 将序列化字符串分割为token
for (char c : data) {
if (c == ',') {
nodes.push(val);
val.clear();
} else {
val.push_back(c);
}
}
return deserializeHelper(nodes);
}
TreeNode* deserializeHelper(queue<string>& nodes) {
string val = nodes.front();
nodes.pop();
if (val == "X") return nullptr; // 空节点
TreeNode* root = new TreeNode(stoi(val));
root->left = deserializeHelper(nodes);
root->right = deserializeHelper(nodes);
return root;
}
【序列化分析】
- 实现思路：使用前序遍历序列化，空节点用特殊符号表示
- ACM应用场景：树的持久化、树的传输与重建
- 多种序列化方案对比：
- 前序遍历序列化（常用）：实现简单，易于理解
- 层序遍历序列化：适合表示广度优先遍历序列
- 括号表示法：如"1(2)(3(4)(5))"，人类可读性好
- 注意事项：
- 确保特殊字符(如X)不会与节点值冲突
- 处理节点值可能包含的特殊字符
- 序列化和反序列化算法必须配对使用
- 优化提示：对于大型树，考虑使用二进制序列化以节省空间
二叉树的高级应用
线索二叉树
线索二叉树是一种优化的二叉树，它利用叶节点的空指针存储前驱和后继信息，以便更高效地进行树的遍历。
// 线索二叉树节点定义
struct ThreadedNode {
int val;
ThreadedNode *left, *right;
bool leftThread; // 左指针是否为线索
bool rightThread; // 右指针是否为线索
ThreadedNode(int x) : val(x), left(nullptr), right(nullptr),
leftThread(false), rightThread(false) {}
};
// 中序线索化二叉树
void inorderThreading(ThreadedNode* root) {
ThreadedNode* prev = nullptr; // 记录前一个访问的节点
inorderThreadingHelper(root, prev);
}
void inorderThreadingHelper(ThreadedNode* node, ThreadedNode*& prev) {
if (node == nullptr) return;
// 线索化左子树
inorderThreadingHelper(node->left, prev);
// 处理当前节点
if (node->left == nullptr) {
node->leftThread = true;
node->left = prev; // 左指针指向前驱
}
// 处理前一个节点的右线索
if (prev != nullptr && prev->right == nullptr) {
prev->rightThread = true;
prev->right = node; // 右指针指向后继
}
prev = node;
// 线索化右子树
inorderThreadingHelper(node->right, prev);
}
【线索二叉树分析】
- 基本原理：利用空指针存储前驱后继，加速遍历
- 优点：无需栈或递归即可进行遍历，空间复杂度O(1)
- 缺点：修改树结构更复杂，需要维护线索信息
- 适用场景：需要频繁遍历但较少修改的二叉树
- ACM竞赛应用：了解即可，实际竞赛中较少直接使用
二叉树的Morris遍历
Morris遍历是一种不使用栈和递归，空间复杂度为O(1)的二叉树遍历算法。
vector<int> morrisInorder(TreeNode* root) {
vector<int> result;
TreeNode* curr = root;
while (curr != nullptr) {
if (curr->left == nullptr) {
// 如果没有左子树，访问当前节点并转向右子树
result.push_back(curr->val);
curr = curr->right;
} else {
// 找到当前节点在中序遍历下的前驱节点
TreeNode* predecessor = curr->left;
while (predecessor->right != nullptr && predecessor->right != curr) {
predecessor = predecessor->right;
}
if (predecessor->right == nullptr) {
// 建立线索（前驱节点的右指针指向当前节点）
predecessor->right = curr;
curr = curr->left;
} else {
// 已经访问过左子树，恢复树结构
predecessor->right = nullptr;
result.push_back(curr->val);
curr = curr->right;
}
}
}
return result;
}
【Morris遍历分析】
- 算法原理：动态建立和拆除线索，无需额外空间
- 关键步骤：
- 找到当前节点的前驱
- 建立临时线索
- 遍历完左子树后拆除线索
- 复杂度分析：
- 时间复杂度：虽然有嵌套循环，但总体仍为O(n)
- 空间复杂度：O(1)，不使用额外空间
- 应用场景：内存受限环境，如嵌入式系统
- ACM提示：这是一种高级技巧，了解原理即可，实际比赛中根据题目选择合适的遍历方式
习题推荐
- LeetCode 94: 二叉树的中序遍历
- LeetCode 102: 二叉树的层序遍历
- LeetCode 105: 从前序与中序遍历序列构造二叉树
- LeetCode 236: 二叉树的最近公共祖先
- LeetCode 662: 二叉树最大宽度
- POJ 1330: 树的最近公共祖先
- Codeforces 380C: Sereja and Brackets（使用二叉树实现的线段树）
- SPOJ QTREE: 树上路径查询系列问题
ACM竞赛实用技巧
二叉树问题解题框架：
- 确定遍历方式（前序、中序、后序、层序）
- 明确是自顶向下还是自底向上解决问题
- 选择合适的递归/迭代方式
输入优化：
// 读入二叉树优化 ios::sync_with_stdio(false); cin.tie(nullptr); // 构建二叉树的常用方法 TreeNode* buildTreeFromArray(const vector<int>& arr, int index = 0) { if (index >= arr.size() || arr[index] == -1) return nullptr; // -1表示空节点 TreeNode* root = new TreeNode(arr[index]); root->left = buildTreeFromArray(arr, 2*index + 1); root->right = buildTreeFromArray(arr, 2*index + 2); return root; }内存管理：
// 清理二叉树内存 void freeTree(TreeNode* root) { if (root == nullptr) return; freeTree(root->left); freeTree(root->right); delete root; } // 比赛中更简单的方法：使用静态数组预分配节点 const int MAXN = 1e5 + 5; TreeNode nodes[MAXN]; int nodeCount = 0; TreeNode* newNode(int val) { nodes[nodeCount].val = val; nodes[nodeCount].left = nodes[nodeCount].right = nullptr; return &nodes[nodeCount++]; }调试技巧：
// 打印二叉树结构（调试用） void printTree(TreeNode* root, string prefix = "", bool isLeft = true) { if (root == nullptr) return; cout << prefix; cout << (isLeft ? "├── " : "└── "); cout << root->val << endl; printTree(root->left, prefix + (isLeft ? "│ " : " "), true); printTree(root->right, prefix + (isLeft ? "│ " : " "), false); }记忆化搜索：对于需要多次重复计算的树形结构问题，使用哈希表缓存中间结果
复杂度分析
平衡二叉搜索树：
- 查找、插入、删除操作的平均时间复杂度：O(log n)
- 最坏情况（如退化为链表）时间复杂度：O(n)
- 存储空间：O(n)
树遍历算法：
- 递归/迭代实现的时间复杂度：O(n)
- 递归/栈实现的空间复杂度：O(h)，h为树高，最坏O(n)
- Morris遍历空间复杂度：O(1)
性能优化策略：
- 对于高度不平衡的树，考虑重新平衡或使用平衡树结构
- 对于频繁查询但很少修改的树，考虑缓存结果
- 递归层数太深时，转为迭代实现避免栈溢出
- 对于大规模数据，使用节点池管理内存，减少动态分配开销
ACM实战注意事项
根据题目规模选择合适的算法实现：
- n ≤ 10^4：普通递归实现通常足够
- n > 10^5：考虑迭代实现或Morris遍历等优化方案
在竞赛环境中，优先使用简单直观的方法，除非题目明确要求优化
处理边界情况：
- 空树
- 只有一个节点的树
- 链状树（只有左子节点或只有右子节点）
- 完全平衡的满二叉树
对于需要频繁重建树的问题，考虑使用静态数组或内存池管理节点，避免反复的动态内存分配和释放