二叉树算法精要：10道经典题目解析与实战技巧

1. 二叉树算法精要从基础到进阶的十道经典题目解析作为一名在算法领域深耕多年的开发者我深知二叉树是面试和实际开发中最常遇到的数据结构之一。今天我将分享LeetCode上110-98题共10道二叉树经典题目的详细解析这些题目覆盖了平衡二叉树、路径查找、树构造、二叉搜索树等核心知识点。不同于简单的题解我会结合多年刷题和面试经验深入讲解每道题的解题思路、易错点和优化技巧。2. 平衡二叉树判定LeetCode 1102.1 问题理解与核心思路平衡二叉树的定义是对于任意一个节点其左右子树高度差的绝对值不超过1。这道题的关键在于如何高效计算每个节点的子树高度并进行比较。重要提示判断平衡二叉树不能简单地比较左右子树高度必须确保所有子树都满足平衡条件。2.2 递归解法详解采用后序遍历左右根的方式是最优选择因为我们需要先知道左右子树的高度才能比较它们的高度差。递归函数的返回值设计是关键class Solution { public: bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; } int getHeight(TreeNode* node) { if (!node) return 0; int left getHeight(node-left); if (left -1) return -1; int right getHeight(node-right); if (right -1) return -1; if (abs(left - right) 1) return -1; return max(left, right) 1; } };2.3 时间复杂度分析与优化时间复杂度O(n)每个节点只访问一次空间复杂度O(h)递归栈空间h为树的高度实际面试中面试官可能会追问是否可以改为迭代解法。虽然可以但代码会复杂很多通常建议优先使用递归解法。3. 二叉树所有路径LeetCode 2573.1 问题分析与解法选择这道题要求找出从根节点到所有叶子节点的路径。两种主要解法递归法DFS代码简洁易于理解迭代法BFS需要维护额外队列3.2 递归实现与回溯技巧class Solution { public: vectorstring binaryTreePaths(TreeNode* root) { vectorstring res; if (root) dfs(root, , res); return res; } void dfs(TreeNode* node, string path, vectorstring res) { path to_string(node-val); if (!node-left !node-right) { res.push_back(path); return; } if (node-left) dfs(node-left, path -, res); if (node-right) dfs(node-right, path -, res); } };3.3 关键点说明回溯的体现每次递归调用传入的是新的path字符串天然实现了回溯路径拼接时机只在访问子节点时才添加-符号终止条件到达叶子节点时将完整路径加入结果集4. 左叶子之和LeetCode 4044.1 左叶子的准确定义很多同学容易混淆左节点和左叶子。左叶子必须满足是某个节点的左孩子自身是叶子节点无左右子节点4.2 递归解法实现class Solution { public: 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); } };4.3 迭代解法示例class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (!root) return 0; stackTreeNode* st; st.push(root); int sum 0; while (!st.empty()) { TreeNode* node st.top(); st.pop(); if (node-left !node-left-left !node-left-right) { sum node-left-val; } if (node-right) st.push(node-right); if (node-left) st.push(node-left); } return sum; } };5. 找树左下角的值LeetCode 5135.1 问题理解与解法对比题目要求找出二叉树最后一层最左边的值。两种主要思路BFS层序遍历直观易于实现DFS递归需要跟踪当前深度5.2 BFS层序遍历实现class Solution { public: int findBottomLeftValue(TreeNode* root) { queueTreeNode* q; q.push(root); int res 0; while (!q.empty()) { int size q.size(); res q.front()-val; for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } } return res; } };5.3 DFS递归解法class Solution { public: int findBottomLeftValue(TreeNode* root) { max_depth -1; dfs(root, 0); return res; } private: int res, max_depth; void dfs(TreeNode* node, int depth) { if (!node) return; if (depth max_depth) { max_depth depth; res node-val; } dfs(node-left, depth 1); dfs(node-right, depth 1); } };6. 路径总和LeetCode 1126.1 问题分析与递归思路判断是否存在从根到叶子的路径使得节点值之和等于给定目标。递归解法最为简洁class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (!root) return false; if (!root-left !root-right) { return targetSum root-val; } return hasPathSum(root-left, targetSum - root-val) || hasPathSum(root-right, targetSum - root-val); } };6.2 迭代解法实现class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (!root) return false; stackpairTreeNode*, int st; st.push({root, root-val}); while (!st.empty()) { auto [node, sum] st.top(); st.pop(); if (!node-left !node-right sum targetSum) { return true; } if (node-right) st.push({node-right, sum node-right-val}); if (node-left) st.push({node-left, sum node-left-val}); } return false; } };7. 从中序与后序遍历构造二叉树LeetCode 1067.1 构造二叉树的核心思路这是二叉树中的经典问题关键在于后序数组的最后一个元素是当前子树的根节点在中序数组中找到这个根节点左边是左子树右边是右子树7.2 递归实现详解class Solution { public: TreeNode* buildTree(vectorint inorder, vectorint postorder) { return helper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1); } TreeNode* helper(vectorint inorder, int inStart, int inEnd, vectorint postorder, int postStart, int postEnd) { if (inStart inEnd) return nullptr; TreeNode* root new TreeNode(postorder[postEnd]); int inRoot inStart; while (inorder[inRoot] ! root-val) inRoot; int leftSize inRoot - inStart; root-left helper(inorder, inStart, inRoot - 1, postorder, postStart, postStart leftSize - 1); root-right helper(inorder, inRoot 1, inEnd, postorder, postStart leftSize, postEnd - 1); return root; } };7.3 时间复杂度与优化时间复杂度O(n^2) 最坏情况每次都要线性搜索根节点优化可以使用哈希表预处理中序数组的位置信息将时间复杂度降到O(n)8. 最大二叉树LeetCode 6548.1 问题理解与递归思路题目要求构造一个最大二叉树其中每个节点的值都大于其子树中的任何其他值。递归解法class Solution { public: TreeNode* constructMaximumBinaryTree(vectorint nums) { return build(nums, 0, nums.size() - 1); } TreeNode* build(vectorint nums, int l, int r) { if (l r) return nullptr; int maxIdx l; for (int i l 1; i r; i) { if (nums[i] nums[maxIdx]) { maxIdx i; } } TreeNode* root new TreeNode(nums[maxIdx]); root-left build(nums, l, maxIdx - 1); root-right build(nums, maxIdx 1, r); return root; } };8.2 单调栈优化解法class Solution { public: TreeNode* constructMaximumBinaryTree(vectorint nums) { vectorTreeNode* stk; for (int num : nums) { TreeNode* node new TreeNode(num); while (!stk.empty() stk.back()-val num) { node-left stk.back(); stk.pop_back(); } if (!stk.empty()) { stk.back()-right node; } stk.push_back(node); } return stk.front(); } };9. 合并二叉树LeetCode 6179.1 递归解法实现class Solution { public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if (!root1) return root2; if (!root2) return root1; root1-val root2-val; root1-left mergeTrees(root1-left, root2-left); root1-right mergeTrees(root1-right, root2-right); return root1; } };9.2 迭代解法示例class Solution { public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if (!root1) return root2; if (!root2) return root1; stackpairTreeNode*, TreeNode* stk; stk.push({root1, root2}); while (!stk.empty()) { auto [node1, node2] stk.top(); stk.pop(); node1-val node2-val; if (node1-left node2-left) { stk.push({node1-left, node2-left}); } else if (!node1-left) { node1-left node2-left; } if (node1-right node2-right) { stk.push({node1-right, node2-right}); } else if (!node1-right) { node1-right node2-right; } } return root1; } };10. 验证二叉搜索树LeetCode 9810.1 中序遍历解法二叉搜索树的中序遍历结果应该是严格递增的class Solution { public: bool isValidBST(TreeNode* root) { TreeNode* prev nullptr; return validate(root, prev); } bool validate(TreeNode* node, TreeNode* prev) { if (!node) return true; if (!validate(node-left, prev)) return false; if (prev prev-val node-val) return false; prev node; return validate(node-right, prev); } };10.2 上下界递归解法class Solution { public: bool isValidBST(TreeNode* root) { return helper(root, LONG_MIN, LONG_MAX); } bool helper(TreeNode* node, long lower, long upper) { if (!node) return true; if (node-val lower || node-val upper) return false; return helper(node-left, lower, node-val) helper(node-right, node-val, upper); } };11. 二叉搜索树中的搜索LeetCode 70011.1 递归解法class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { if (!root || root-val val) return root; return val root-val ? searchBST(root-left, val) : searchBST(root-right, val); } };11.2 迭代解法class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { while (root root-val ! val) { root val root-val ? root-left : root-right; } return root; } };12. 二叉树算法实战经验总结经过这10道题目的详细解析我总结出以下二叉树算法的重要经验遍历顺序选择前序根→左→右适合自上而下的操作中序左→根→右BST相关操作后序左→右→根需要子树信息时层序按层次遍历找每层最值递归与迭代的选择递归代码简洁但可能有栈溢出风险迭代需要手动维护栈/队列但空间复杂度可能更优边界条件处理空节点处理单节点处理左右子树不对称情况性能优化方向记忆化重复计算提前终止不必要的递归使用哈希表加速查找常见错误混淆节点引用和节点拷贝忘记处理空指针递归终止条件不完整在实际面试中建议先明确问题要求然后与面试官讨论解题思路最后再编码实现。对于二叉树问题递归解法通常是首选但也要准备好迭代解法作为备选。