1. 力扣刷题实战：四道经典二叉树问题解析（C++实现）
最近在系统刷力扣的二叉树专题，发现110、257、404、222这四道题特别有代表性，涵盖了平衡判断、路径记录、左叶求和和节点计数等核心考点。今天就用C++带大家手撕这四道题，分享我的解题思路和踩坑经验。
2. 解题环境准备与基础框架
2.1 二叉树节点定义
所有题目都基于相同的二叉树节点结构：
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) {} };2.2 递归与迭代的选择策略
- 递归：代码简洁，适合对称性问题和路径追踪
- 迭代：显式栈/队列更直观，适合层序遍历和特定顺序访问
- 本系列优先展示递归解法，同时提供迭代思路
3. 题目110：平衡二叉树判断
3.1 问题重述
给定二叉树，判断它是否是高度平衡的（左右子树高度差≤1）
3.2 自顶向下解法（初版）
int height(TreeNode* root) { if (!root) return 0; return 1 + max(height(root->left), height(root->right)); } bool isBalanced(TreeNode* root) { if (!root) return true; return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right); }问题：存在重复计算，时间复杂度O(nlogn)
3.3 优化版（自底向上）
int checkHeight(TreeNode* root) { if (!root) return 0; int left = checkHeight(root->left); if (left == -1) return -1; int right = checkHeight(root->right); if (right == -1) return -1; if (abs(left - right) > 1) return -1; return 1 + max(left, right); } bool isBalanced(TreeNode* root) { return checkHeight(root) != -1; }关键改进：在计算高度时直接判断平衡性，时间复杂度优化到O(n)
4. 题目257：二叉树所有路径
4.1 问题要求
返回所有从根节点到叶节点的路径（如["1->2->5","1->3"]）
4.2 回溯法实现
void constructPaths(TreeNode* root, string path, vector<string>& paths) { if (!root) return; path += to_string(root->val); if (!root->left && !root->right) { paths.push_back(path); return; } path += "->"; constructPaths(root->left, path, paths); constructPaths(root->right, path, paths); } vector<string> binaryTreePaths(TreeNode* root) { vector<string> paths; constructPaths(root, "", paths); return paths; }4.3 迭代法实现（栈模拟）
vector<string> binaryTreePaths(TreeNode* root) { vector<string> paths; if (!root) return paths; stack<pair<TreeNode*, string>> s; s.push({root, ""}); while (!s.empty()) { auto [node, path] = s.top(); s.pop(); path += to_string(node->val); if (!node->left && !node->right) { paths.push_back(path); } else { path += "->"; if (node->right) s.push({node->right, path}); if (node->left) s.push({node->left, path}); } } return paths; }5. 题目404：左叶子之和
5.1 关键定义
左叶子节点需满足：
- 是父节点的左孩子
- 自身是叶子节点（无左右子树）
5.2 递归解法
int sumOfLeftLeaves(TreeNode* root) { if (!root) return 0; int sum = 0; if (root->left && !root->left->left && !root->left->right) { sum += root->left->val; } return sum + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right); }5.3 迭代解法（前序遍历）
int sumOfLeftLeaves(TreeNode* root) { if (!root) return 0; stack<TreeNode*> s; s.push(root); int sum = 0; while (!s.empty()) { TreeNode* node = s.top(); s.pop(); if (node->left) { if (!node->left->left && !node->left->right) { sum += node->left->val; } else { s.push(node->left); } } if (node->right) { s.push(node->right); } } return sum; }6. 题目222：完全二叉树的节点个数
6.1 普通二叉树解法（通用）
int countNodes(TreeNode* root) { if (!root) return 0; return 1 + countNodes(root->left) + countNodes(root->right); }6.2 利用完全二叉树特性的优化
int countNodes(TreeNode* root) { if (!root) return 0; int leftHeight = 0, rightHeight = 0; TreeNode* l = root, *r = root; while (l) { leftHeight++; l = l->left; } while (r) { rightHeight++; r = r->right; } if (leftHeight == rightHeight) { return (1 << leftHeight) - 1; // 2^h - 1 } return 1 + countNodes(root->left) + countNodes(root->right); }时间复杂度：O(logN * logN)，利用完全二叉树特性大幅优化
7. 调试技巧与常见错误
7.1 二叉树调试工具函数
// 层次打印二叉树（调试用） void printTree(TreeNode* root) { if (!root) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; ++i) { TreeNode* node = q.front(); q.pop(); cout << node->val << " "; if (node->left) q.push(node->left); if (node->right) q.push(node->right); } cout << endl; } }7.2 常见错误排查表
| 错误现象 | 可能原因 | 解决方案 |
|---|---|---|
| 平衡判断错误 | 忽略子树也需要平衡 | 递归检查每棵子树 |
| 路径重复记录 | 未及时回溯path变量 | 使用string传值而非引用 |
| 左叶误判 | 未检查父节点关系 | 增加父节点指针或标记 |
| 计数超时 | 未利用完全二叉树特性 | 先计算左右子树高度 |
8. 性能对比与进阶思考
8.1 四题解法性能对比
| 题号 | 暴力解法 | 优化解法 | 提升幅度 |
|---|---|---|---|
| 110 | O(nlogn) | O(n) | 10x (n=10000) |
| 257 | O(n) | O(n) | 代码更简洁 |
| 404 | O(n) | O(n) | 迭代节省栈空间 |
| 222 | O(n) | O(log²n) | 100x (n=1e5) |
8.2 相似题目扩展
- 111题：最小深度（注意与最大深度的区别）
- 112题：路径总和（回溯法的经典应用）
- 226题：翻转二叉树（分治思想入门）
- 543题：二叉树直径（高度计算的变种）
在实际面试中，建议先确认二叉树的类型（普通/完全/满），再选择最优解法。对于平衡二叉树问题，微软和亚马逊常考变形题；路径问题则是字节跳动的常见题型。
