企业网站设计行业,网站如何安装源码,设计师网站建设,创建网站得花多少钱文章目录 题目标题和出处难度题目描述要求示例数据范围 前言解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;路径总和 II
出处#xff1a;113. 路径总和 II
难度
4 级
题目描述
要求
给你二叉树的根结点 root \tex… 文章目录 题目标题和出处难度题目描述要求示例数据范围 前言解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题路径总和 II
出处113. 路径总和 II
难度
4 级
题目描述
要求
给你二叉树的根结点 root \texttt{root} root 和一个表示目标和的整数 targetSum \texttt{targetSum} targetSum返回所有的满足路径上结点值总和等于目标和 targetSum \texttt{targetSum} targetSum 的从根结点到叶结点的路径。每条路径应该以结点值列表的形式返回而不是结点的引用。
示例
示例 1 输入 root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22 \texttt{root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22} root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22 输出 [[5,4,11,2],[5,8,4,5]] \texttt{[[5,4,11,2],[5,8,4,5]]} [[5,4,11,2],[5,8,4,5]] 解释有两条路径的结点值总和等于 targetSum \texttt{targetSum} targetSum 5 4 11 2 22 \texttt{5 4 11 2 22} 5 4 11 2 22 5 8 4 5 22 \texttt{5 8 4 5 22} 5 8 4 5 22
示例 2 输入 root [1,2,3], targetSum 5 \texttt{root [1,2,3], targetSum 5} root [1,2,3], targetSum 5 输出 [] \texttt{[]} []
示例 3
输入 root [1,2], targetSum 0 \texttt{root [1,2], targetSum 0} root [1,2], targetSum 0 输出 [] \texttt{[]} []
数据范围
树中结点数目在范围 [0, 5000] \texttt{[0, 5000]} [0, 5000] 内 -1000 ≤ Node.val ≤ 1000 \texttt{-1000} \le \texttt{Node.val} \le \texttt{1000} -1000≤Node.val≤1000 -1000 ≤ targetSum ≤ 1000 \texttt{-1000} \le \texttt{targetSum} \le \texttt{1000} -1000≤targetSum≤1000
前言
这道题是「路径总和」的进阶要求返回所有的结点值总和等于目标和的从根结点到叶结点的路径。这道题也可以使用深度优先搜索和广度优先搜索得到答案在搜索过程中需要维护路径。
解法一
思路和算法
如果二叉树为空则不存在结点值总和等于目标和的路径。只有当二叉树不为空时才可能存在结点值总和等于目标和的路径需要从根结点开始寻找路径。
从根结点开始深度优先搜索在遍历每一个结点的同时需要维护从根结点到当前结点的路径以及剩余目标和将原目标和减去当前结点值即可得到剩余目标和。当访问到叶结点时如果剩余目标和为 0 0 0则从根结点到当前叶结点的路径即为结点值总和等于目标和的路径将该路径添加到结果列表中。
由于深度优先搜索过程中维护的路径会随着访问到的结点而变化因此当找到结点值总和等于目标和的路径时需要新建一个路径对象添加到结果列表中避免后续搜索过程中路径变化对结果造成影响。
代码
class Solution {ListListInteger paths new ArrayListListInteger();ListInteger path new ArrayListInteger();public ListListInteger pathSum(TreeNode root, int targetSum) {dfs(root, targetSum);return paths;}public void dfs(TreeNode node, int targetSum) {if (node null) {return;}path.add(node.val);targetSum - node.val;if (node.left null node.right null targetSum 0) {paths.add(new ArrayListInteger(path));}dfs(node.left, targetSum);dfs(node.right, targetSum);path.remove(path.size() - 1);}
}复杂度分析 时间复杂度 O ( n 2 ) O(n^2) O(n2)其中 n n n 是二叉树的结点数。每个结点都被访问一次最坏情况下每次将路径添加到结果中的时间是 O ( n ) O(n) O(n)因此总时间复杂度是 O ( n 2 ) O(n^2) O(n2)。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间以及深度优先搜索过程中存储路径的空间取决于二叉树的高度最坏情况下二叉树的高度是 O ( n ) O(n) O(n)。注意返回值不计入空间复杂度。
解法二
思路和算法
使用广度优先搜索寻找结点值总和等于目标和的路径时首先找到这些路径对应的叶结点然后得到从叶结点到根结点的路径将路径翻转之后即可得到相应的路径。
为了得到从叶结点到根结点的路径需要使用哈希表存储每个结点的父结点在广度优先搜索的过程中即可将每个结点和父结点的关系存入哈希表中。
广度优先搜索需要维护两个队列分别存储结点与对应的结点值总和。广度优先搜索的过程中如果遇到一个叶结点对应的结点值总和等于目标和则找到一条结点值总和等于目标和的路径利用哈希表中存储的父结点信息得到从当前叶结点到根结点的路径然后将路径翻转添加到结果中。
代码
class Solution {ListListInteger paths new ArrayListListInteger();MapTreeNode, TreeNode parents new HashMapTreeNode, TreeNode();public ListListInteger pathSum(TreeNode root, int targetSum) {if (root null) {return paths;}QueueTreeNode nodeQueue new ArrayDequeTreeNode();QueueInteger sumQueue new ArrayDequeInteger();nodeQueue.offer(root);sumQueue.offer(root.val);while (!nodeQueue.isEmpty()) {TreeNode node nodeQueue.poll();int sum sumQueue.poll();TreeNode left node.left, right node.right;if (left null right null sum targetSum) {paths.add(getPath(node));}if (left ! null) {parents.put(left, node);nodeQueue.offer(left);sumQueue.offer(sum left.val);}if (right ! null) {parents.put(right, node);nodeQueue.offer(right);sumQueue.offer(sum right.val);}}return paths;}public ListInteger getPath(TreeNode node) {ListInteger path new ArrayListInteger();while (node ! null) {path.add(node.val);node parents.get(node);}Collections.reverse(path);return path;}
}复杂度分析 时间复杂度 O ( n 2 ) O(n^2) O(n2)其中 n n n 是二叉树的结点数。每个结点都被访问一次最坏情况下每次将路径添加到结果中的时间是 O ( n ) O(n) O(n)因此总时间复杂度是 O ( n 2 ) O(n^2) O(n2)。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。空间复杂度主要是哈希表和队列空间哈希表需要存储每个结点的父结点需要 O ( n ) O(n) O(n) 的空间两个队列内元素个数都不超过 n n n。注意返回值不计入空间复杂度。
