做建设网站的活的兼职,百度网盘登录入口 网页,棋牌网站怎么做,网站建设项目报告一、题目描述
给你二叉树的根节点 root 和一个整数目标和 targetSum #xff0c;找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。 示例 1#xff1a; 输入#xff1a;root [5,4,8,11,null,13,4,7,2,null,null,5,1], target…一、题目描述
给你二叉树的根节点 root 和一个整数目标和 targetSum 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。 示例 1 输入root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22
输出[[5,4,11,2],[5,8,4,5]]示例 2 输入root [1,2,3], targetSum 5
输出[]示例 3
输入root [1,2], targetSum 0
输出[]提示
树中节点总数在范围 [0, 5000] 内-1000 Node.val 1000-1000 targetSum 1000
二、解题思路
这个问题可以通过递归的方式解决。我们定义一个递归函数该函数接受当前节点和当前路径和作为参数。递归函数的工作流程如下
1. 如果当前节点是空返回一个空列表。
2. 如果当前节点是叶子节点即没有子节点检查当前路径和是否等于目标值。如果是将当前路径和加入到结果列表中。
3. 如果当前节点不是叶子节点递归地调用函数
调用函数参数是当前节点的左子节点和当前路径和加上当前节点的值。调用函数参数是当前节点的右子节点和当前路径和加上当前节点的值。
4. 将两个递归调用中的结果合并到一起并返回。
三、具体代码
class Solution {public ListListInteger pathSum(TreeNode root, int targetSum) {ListListInteger result new ArrayList();if (root null) {return result;}pathSum(root, targetSum, new ArrayList(), result);return result;}private void pathSum(TreeNode node, int target, ListInteger currentPath, ListListInteger result) {if (node null) {return;}currentPath.add(node.val);if (node.left null node.right null target node.val) {result.add(new ArrayList(currentPath));}pathSum(node.left, target - node.val, currentPath, result);pathSum(node.right, target - node.val, currentPath, result);currentPath.remove(currentPath.size() - 1);}
}四、时间复杂度和空间复杂度
1. 时间复杂度 递归函数调用次数对于每个节点我们最多会调用一次 pathSum 函数。因此对于一个有 n 个节点的树最坏情况下函数会被调用 n 次。 单次递归调用的时间复杂度对于每个节点的单次递归调用我们需要执行常数时间操作如判断当前节点是否为空、更新当前路径、判断是否为叶子节点以及添加结果等。 综上所述总的时间复杂度是 O(n)其中 n 是树中节点的数量。
2. 空间复杂度 递归调用栈递归调用会使用系统栈来存储每一层递归的信息。在最坏的情况下树可能是一个完全二叉树此时递归调用栈的深度为 O(h)其中 h 是树的高度。 其他空间除了递归调用栈之外我们不需要额外的空间来存储节点的信息因此这部分的空间复杂度是 O(1)。 综上所述总的空间复杂度是 O(h)在最坏情况下是 O(n)。
五、总结知识点 递归函数pathSum 函数是一个递归函数它接受当前节点、目标和当前路径作为参数并递归地检查左子树和右子树。 二叉树的遍历通过递归的方式代码实现了对二叉树的遍历从根节点开始逐层向下直到到达叶子节点。 路径和的概念代码中维护了一个变量 currentPath用于跟踪从根节点到当前节点的路径上所有节点值之和。 叶子节点的判断通过检查当前节点的左右子节点是否都为空来确定一个节点是否是叶子节点。 条件语句代码中使用了 if 条件语句来判断节点是否为空、是否为叶子节点以及路径和是否等于目标值。 递归终止条件递归函数在遇到空节点时返回这是递归的终止条件。 逻辑运算符代码中使用了逻辑运算符 || 来组合两个递归调用如果任意一个调用返回 true则整个表达式返回 true。 函数的封装pathSum 函数被定义为 private这意味着它只能在同一个类中被访问这是封装的一种形式。 树的表示代码中使用了 TreeNode 类来定义二叉树的节点这是二叉树数据结构的基本表示方法。 列表的使用代码中使用了 ArrayList 类来存储路径和结果这是一种动态数组可以方便地添加和删除元素。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
