力扣二叉树四题解析：平衡判断与路径记录（C++实现）

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 问题重述给定二叉树判断它是否是高度平衡的左右子树高度差≤13.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, vectorstring 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); } vectorstring binaryTreePaths(TreeNode* root) { vectorstring paths; constructPaths(root, , paths); return paths; }4.3 迭代法实现栈模拟vectorstring binaryTreePaths(TreeNode* root) { vectorstring paths; if (!root) return paths; stackpairTreeNode*, 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; stackTreeNode* 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; queueTreeNode* 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 四题解法性能对比题号暴力解法优化解法提升幅度110O(nlogn)O(n)10x (n10000)257O(n)O(n)代码更简洁404O(n)O(n)迭代节省栈空间222O(n)O(log²n)100x (n1e5)8.2 相似题目扩展111题最小深度注意与最大深度的区别112题路径总和回溯法的经典应用226题翻转二叉树分治思想入门543题二叉树直径高度计算的变种在实际面试中建议先确认二叉树的类型普通/完全/满再选择最优解法。对于平衡二叉树问题微软和亚马逊常考变形题路径问题则是字节跳动的常见题型。