网站页面设计流程,怎么做简单网站首页,wordpress调用指定分类文章,typecho 企业网站Leetcode 112: 路径总和
问题描述#xff1a; 给定一个二叉树的根节点 root 和一个目标和 targetSum#xff0c;判断是否存在从根节点到叶子节点的路径#xff0c;使路径上所有节点的值相加等于目标和 targetSum。 适合面试的解法#xff1a;递归
解法特点#xff1a;
…Leetcode 112: 路径总和
问题描述 给定一个二叉树的根节点 root 和一个目标和 targetSum判断是否存在从根节点到叶子节点的路径使路径上所有节点的值相加等于目标和 targetSum。 适合面试的解法递归
解法特点
递归是解决路径和问题的最优实现方式利用二叉树的递归性质逐步处理每条可能的路径。对每个节点递归减去当前节点的值直到叶子节点时检查剩余的 targetSum 是否为零。时间复杂度 (O(n))空间复杂度 (O(h))(h) 为树的高度递归栈的深度非常适合面试场景。 解法思路
核心步骤 递归分治 当前节点的路径总和由其左子树和右子树是否有满足条件的路径决定。每次递归将 targetSum 减去当前节点的值抵达叶子时检查剩余的和。 判断叶子节点 如果当前节点是叶子节点无左子节点也无右子节点同时路径总和符合 targetSum返回 true。 递归终止条件 如果当前节点为 null返回 false。叶子节点时检查 targetSum 是否与节点值相等。 最终逻辑 对每个节点递归判断它的左子树和右子树是否满足条件。 代码模板递归法
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {// Step 1: 如果节点为空返回 falseif (root null) {return false;}// Step 2: 如果节点是叶子节点检查是否路径总和满足条件if (root.left null root.right null) {return root.val targetSum;}// Step 3: 减去当前节点值从左右子树递归查找路径和int remainingSum targetSum - root.val;return hasPathSum(root.left, remainingSum) || hasPathSum(root.right, remainingSum);}
}代码详细注释
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {// Step 1: 递归终止条件// 如果当前节点为 null没有路径可以满足条件返回 falseif (root null) {return false;}// Step 2: 检查叶子节点// 如果当前节点是叶子节点无左右子节点检查路径总和是否满足 targetSumif (root.left null root.right null) {return root.val targetSum; // 如果满足条件返回 true}// Step 3: 递归处理子树// 更新剩余的路径总和递归查找左右子树int remainingSum targetSum - root.val;boolean leftResult hasPathSum(root.left, remainingSum); // 检查左子树路径总和boolean rightResult hasPathSum(root.right, remainingSum); // 检查右子树路径总和// Step 4: 返回结果// 如果任意一个子树满足路径总和条件返回 truereturn leftResult || rightResult;}
}复杂度分析
时间复杂度
每个节点最多被访问一次时间复杂度为 (O(n))其中 (n) 是树的节点总数。
空间复杂度
递归栈的深度与树的高度相关 平衡二叉树的高度为 (O(\log n))空间复杂度为 (O(\log n))。完全不平衡二叉树链表状的高度为 (O(n))空间复杂度为 (O(n))。 测试用例
示例 1
输入
root [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum 22输出
true解释 从根节点到叶子节点的一条路径 5 → 4 → 11 → 2 的总和等于 22。 示例 2
输入
root [1,2,3], targetSum 5输出
false解释 树中任意路径的总和都不等于 5。 示例 3
输入
root [], targetSum 0输出
false如何快速 AC面试技巧
1. 树的递归分治思想
每个节点的路径和问题可以归结为子树的路径和问题递归很自然地处理二叉树。
2. 判断叶子节点的条件
特别强调叶子节点的判断逻辑必须满足“无左右子节点”且“路径和符合目标 sum”。
3. 时间复杂度分析
(O(n))每节点访问一次这是二叉树递归常见的复杂度。空间复杂度根据树的高度合理优化。
4. 全局逻辑清晰表达
用递归逻辑分解问题每一层会贡献新的 targetSum剩余路径和。 其他解法
方法 2迭代法使用栈
思路
使用栈实现递归的效果根据路径累加值判断是否符合 targetSum。
代码模板
import java.util.*;class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root null) return false; // 如果树为空直接返回 false// 初始化栈用于模拟递归逻辑StackTreeNode nodeStack new Stack();StackInteger sumStack new Stack();nodeStack.push(root);sumStack.push(targetSum);// 遍历节点while (!nodeStack.isEmpty()) {TreeNode currentNode nodeStack.pop();int currentSum sumStack.pop() - currentNode.val;// 如果是叶子节点检查路径是否满足条件if (currentNode.left null currentNode.right null currentSum 0) {return true;}// 将左右子节点入栈更新路径和if (currentNode.right ! null) {nodeStack.push(currentNode.right);sumStack.push(currentSum);}if (currentNode.left ! null) {nodeStack.push(currentNode.left);sumStack.push(currentSum);}}return false;}
}对比递归与迭代
解法时间复杂度空间复杂度适用场景递归法(O(n))(O(h))简单树结构逻辑直观迭代法(O(n))(O(h))栈存储深度较大的树避免递归栈溢出 推荐解法递归法
适合面试场景
递归法易于实现逻辑直观时间复杂度和空间复杂度表现良好。 总结如何快速 AC
使用递归实现树的递归逻辑清晰。判断叶子节点时特别强调路径和条件。时间复杂度和空间复杂度分析简洁明了边界处理完整。
通过递归方法你可以快速实现并解决问题同时展示对二叉树递归的掌握非常适合面试场景
