1. 二叉树基础与字符串表示
在C++中处理二叉树问题时，最基础也最容易被忽视的就是如何正确表示树结构。我们先来看一个看似简单但暗藏玄机的问题：根据二叉树创建字符串。
1.1 问题描述与示例分析
LeetCode 606题要求我们将二叉树按照特定规则转换为字符串表示。规则如下：
- 空节点用空字符串表示
- 非空节点用其值表示
- 对于每个非空节点：
- 如果只有右孩子，左孩子的空括号不能省略
- 如果只有左孩子，可以省略右孩子的空括号
举个例子：
1 / \ 2 3 / 4应该表示为"1(2(4))(3)"，而不是"1(2(4)())(3())"。
1.2 递归解法实现
这个问题的经典解法是递归遍历，但有几个关键细节需要注意：
class Solution { public: string tree2str(TreeNode* root) { if (!root) return ""; string res = to_string(root->val); // 关键判断1：左子树为空但右子树不空时 if (!root->left && root->right) { res += "()"; } // 关键判断2：左子树不空时 if (root->left) { res += "(" + tree2str(root->left) + ")"; } // 关键判断3：右子树不空时 if (root->right) { res += "(" + tree2str(root->right) + ")"; } return res; } };注意：to_string()函数在转换节点值时可能会成为性能瓶颈，对于高频调用场景建议预先分配缓冲区。
1.3 迭代解法优化
递归解法虽然直观，但在处理大型树时可能引发栈溢出。我们可以用栈模拟递归过程：
string tree2str_iterative(TreeNode* root) { if (!root) return ""; stack<TreeNode*> st; st.push(root); unordered_set<TreeNode*> visited; string res; while (!st.empty()) { TreeNode* node = st.top(); if (visited.count(node)) { st.pop(); res += ")"; } else { visited.insert(node); res += "(" + to_string(node->val); // 处理右左子树的顺序 if (!node->left && node->right) res += "()"; if (node->right) st.push(node->right); if (node->left) st.push(node->left); } } return res.substr(1, res.size()-2); }这种解法虽然代码量增加，但避免了递归深度限制，适合生产环境使用。
2. 最近公共祖先问题
2.1 LCA问题定义
最近公共祖先(Lowest Common Ancestor)是二叉树中的经典问题。给定两个节点p和q，找到它们在树中最低的公共祖先节点。
2.2 递归解法分析
最直观的解法是通过递归搜索：
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || root == p || root == q) return root; TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if (left && right) return root; return left ? left : right; }这个解法的时间复杂度是O(n)，空间复杂度最坏情况下也是O(n)。
2.3 非递归解法实现
我们可以使用父指针记录法来优化：
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { unordered_map<TreeNode*, TreeNode*> parent; stack<TreeNode*> st; parent[root] = nullptr; st.push(root); // 构建父指针映射 while (!parent.count(p) || !parent.count(q)) { TreeNode* node = st.top(); st.pop(); if (node->left) { parent[node->left] = node; st.push(node->left); } if (node->right) { parent[node->right] = node; st.push(node->right); } } // 收集p的祖先路径 set<TreeNode*> ancestors; while (p) { ancestors.insert(p); p = parent[p]; } // 查找q的祖先中第一个出现在p路径中的节点 while (!ancestors.count(q)) { q = parent[q]; } return q; }这种方法虽然空间复杂度略高，但在多次查询时可以复用父指针映射，适合查询密集型场景。
3. 二叉搜索树与双向链表
3.1 问题转换思路
将二叉搜索树转换为排序的双向链表，要求不能创建新节点，只能调整指针指向。这是一个典型的树与链表转换问题。
3.2 中序遍历解法
利用BST的中序遍历特性，我们可以得到有序序列：
class Solution { TreeNode* prev = nullptr; TreeNode* head = nullptr; public: TreeNode* treeToDoublyList(TreeNode* root) { if (!root) return nullptr; inorder(root); // 连接首尾形成循环 head->left = prev; prev->right = head; return head; } void inorder(TreeNode* node) { if (!node) return; inorder(node->left); if (!prev) { head = node; // 记录链表头 } else { prev->right = node; node->left = prev; } prev = node; inorder(node->right); } };注意：在面试中常被问及非递归实现，建议同时掌握迭代版本。
3.3 迭代实现版本
TreeNode* treeToDoublyList_iterative(TreeNode* root) { if (!root) return nullptr; stack<TreeNode*> st; TreeNode *head = nullptr, *prev = nullptr; TreeNode* curr = root; while (curr || !st.empty()) { while (curr) { st.push(curr); curr = curr->left; } curr = st.top(); st.pop(); if (!prev) { head = curr; } else { prev->right = curr; curr->left = prev; } prev = curr; curr = curr->right; } // 连接首尾 head->left = prev; prev->right = head; return head; }4. 前序与中序构建二叉树
4.1 重建二叉树原理
给定前序和中序遍历序列，可以唯一确定一棵二叉树。前序的第一个元素是根节点，中序中该元素左边是左子树，右边是右子树。
4.2 递归实现
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { unordered_map<int, int> inMap; for (int i = 0; i < inorder.size(); i++) { inMap[inorder[i]] = i; } return build(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1, inMap); } TreeNode* build(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd, unordered_map<int, int>& inMap) { if (preStart > preEnd || inStart > inEnd) return nullptr; TreeNode* root = new TreeNode(preorder[preStart]); int inRoot = inMap[root->val]; int numsLeft = inRoot - inStart; root->left = build(preorder, preStart+1, preStart+numsLeft, inorder, inStart, inRoot-1, inMap); root->right = build(preorder, preStart+numsLeft+1, preEnd, inorder, inRoot+1, inEnd, inMap); return root; }4.3 迭代实现优化
递归解法在极端情况下可能导致栈溢出，我们可以用栈来模拟递归过程：
TreeNode* buildTree_iterative(vector<int>& preorder, vector<int>& inorder) { if (preorder.empty()) return nullptr; stack<TreeNode*> st; TreeNode* root = new TreeNode(preorder[0]); st.push(root); int inIndex = 0; for (int i = 1; i < preorder.size(); i++) { TreeNode* node = st.top(); if (node->val != inorder[inIndex]) { node->left = new TreeNode(preorder[i]); st.push(node->left); } else { while (!st.empty() && st.top()->val == inorder[inIndex]) { node = st.top(); st.pop(); inIndex++; } node->right = new TreeNode(preorder[i]); st.push(node->right); } } return root; }5. 二叉树的非递归遍历
5.1 前序遍历的非递归实现
vector<int> preorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; if (root) st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); res.push_back(node->val); // 注意右子树先入栈 if (node->right) st.push(node->right); if (node->left) st.push(node->left); } return res; }5.2 中序遍历的非递归实现
vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; TreeNode* curr = root; while (curr || !st.empty()) { while (curr) { st.push(curr); curr = curr->left; } curr = st.top(); st.pop(); res.push_back(curr->val); curr = curr->right; } return res; }5.3 后序遍历的非递归实现
后序遍历是最复杂的，需要记录访问状态：
vector<int> postorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; TreeNode* lastVisited = nullptr; TreeNode* curr = root; while (curr || !st.empty()) { if (curr) { st.push(curr); curr = curr->left; } else { TreeNode* peek = st.top(); if (peek->right && peek->right != lastVisited) { curr = peek->right; } else { res.push_back(peek->val); lastVisited = peek; st.pop(); } } } return res; }5.4 统一迭代法模板
为了统一三种遍历方式，可以使用标记法：
// 前序遍历 vector<int> preorderTraversal_unified(TreeNode* root) { vector<int> res; stack<TreeNode*> st; if (root) st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); if (node) { if (node->right) st.push(node->right); // 右 if (node->left) st.push(node->left); // 左 st.push(node); // 中 st.push(nullptr); // 标记 } else { node = st.top(); st.pop(); res.push_back(node->val); } } return res; }只需调整入栈顺序，即可实现三种遍历的统一模板。
6. 二叉树问题实战技巧
6.1 调试与可视化
在处理复杂二叉树问题时，可视化工具能极大提升效率。可以自定义打印函数：
void printTree(TreeNode* root, int space = 0, int height = 10) { if (!root) return; space += height; printTree(root->right, space); cout << endl; for (int i = height; i < space; i++) cout << ' '; cout << root->val << "\n"; printTree(root->left, space); }6.2 内存管理注意事项
在面试或竞赛中，经常需要手动管理二叉树内存：
void deleteTree(TreeNode* root) { if (!root) return; deleteTree(root->left); deleteTree(root->right); delete root; }6.3 常见错误排查
- 空指针异常：总是检查节点是否为null
- 无限递归：确保递归有终止条件
- 错误的状态维护：在非递归遍历中正确维护栈状态
- 指针修改错误：在链表转换问题中注意指针修改顺序
6.4 性能优化建议
- 对于高频调用的辅助函数，考虑使用静态变量缓存结果
- 在递归解法中，尽可能使用尾递归优化
- 对于大型树，优先考虑迭代解法避免栈溢出
- 使用哈希表存储中间结果，减少重复计算
7. 二叉树扩展问题
7.1 序列化与反序列化
// 序列化为字符串 string serialize(TreeNode* root) { if (!root) return "#"; return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right); } // 从字符串反序列化 TreeNode* deserialize(string data) { queue<string> q; string s; for (char c : data) { if (c == ',') { q.push(s); s = ""; } else { s += c; } } if (!s.empty()) q.push(s); return helper(q); } TreeNode* helper(queue<string>& q) { string s = q.front(); q.pop(); if (s == "#") return nullptr; TreeNode* root = new TreeNode(stoi(s)); root->left = helper(q); root->right = helper(q); return root; }7.2 验证二叉搜索树
bool isValidBST(TreeNode* root) { stack<TreeNode*> st; TreeNode* prev = nullptr; TreeNode* curr = root; while (curr || !st.empty()) { while (curr) { st.push(curr); curr = curr->left; } curr = st.top(); st.pop(); if (prev && prev->val >= curr->val) return false; prev = curr; curr = curr->right; } return true; }7.3 二叉树的最大路径和
int maxPathSum(TreeNode* root) { int maxSum = INT_MIN; helper(root, maxSum); return maxSum; } int helper(TreeNode* node, int& maxSum) { if (!node) return 0; int left = max(helper(node->left, maxSum), 0); int right = max(helper(node->right, maxSum), 0); maxSum = max(maxSum, left + right + node->val); return max(left, right) + node->val; }在实际工程中，二叉树问题的解决往往需要结合具体业务场景进行调整。建议在掌握这些经典算法的基础上，多思考如何将它们应用到实际问题中。例如，文件系统的目录结构、组织架构图、决策树等都可以用二叉树模型来表示和处理。
