-
LeetCode二叉树路径和
2020-02-05 16:44:25找出路径和等于给定数值的路径总数。 路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。 二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] ...LeetCode双重递归
记录第一篇博客,养成好习惯
题目描述
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
示例:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/
5 -3
/ \
3 2 11
/ \
3 -2 1返回 3。和等于 8 的路径有:
- 5 -> 3
- 5 -> 2 -> 1
- -3 -> 11
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/path-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。题解
思路
1.在题干的描述中难点在于路径不需要从根节点开始,也不需要在叶子节点结束
1)不妨先考虑路径必须要从根节点开始再到叶节点结束,记录路径中满足sum的路径和,这就会构成第一层递归
此时遍历在叶节点结束,但构成sum的路径不一定结束在叶节点
2)将每个遍历到的节点都看作根节点,则构成第二层递归
此时每个遍历到的节点,则会实现不一定从根节点出发
代码(Python实现)
class Solution(object): #第一层递归,类似于树的中序遍历 #实现:让遍历到的每个节点,依次作为根节点 def pathSum(self, root, sum): pathNum=0 if root!=None and root.val!=None: pathNum=pathNum+self.fun(root,sum) pathNum=pathNum+self.pathSum(root.left,sum) pathNum=pathNum+self.pathSum(root.right,sum) return pathNum #第二层递归 #实现:找出从root节点出发到叶节点过程中,和为tempSum的路径总和 #(注意此处的tempSum与题干中要求的sum并不相同) def fun(self,root,tempSum): pathNum=0 if root!=None: tempSum=tempSum-root.val if tempSum==0: #此时可能还未到达叶节点 pathNum=pathNum+1 pathNum=pathNum+ self.fun(root.left,tempSum)+ self.fun(root.right,tempSum) return pathNum
-
leetcode 二叉树路径和 path sum
2019-02-19 11:18:35这道二叉树路径之和在之前的基础上又需要找出路径 ,但是基本思想都一样,还是需要用深度优先搜索DFS,只不过数据结构相对复杂一点,需要用到二维的vector,而且每当DFS搜索到新节点时,都要保存该节点。而且每当找...1.
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree andsum = 22
,5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool dfs(TreeNode *node, int sum, int curSum) { if (node == NULL) return false; if (node->left == NULL && node->right == NULL) return curSum + node->val == sum; return dfs(node->left, sum, curSum + node->val) || dfs(node->right, sum, curSum + node->val); } bool hasPathSum(TreeNode *root, int sum) { return dfs(root, sum, 0); } };
/** * Definition for binary tree * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool dfs(struct TreeNode *node, int sum, int cur); bool hasPathSum(struct TreeNode *root, int sum) { return dfs(root, sum, 0); } bool dfs(struct TreeNode *node, int sum, int cur){ if(node == NULL) return false; if(node->left == NULL && node->right == NULL) return cur+node->val == sum; return(dfs(node->left, sum, cur+node->val) || dfs(node->right, sum, cur+node->val)); }
2.路径和,打印路径
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree andsum = 22
,5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
return
[ [5,4,11,2], [5,8,4,5] ] 这道二叉树路径之和在之前的基础上又需要找出路径 ,但是基本思想都一样,还是需要用深度优先搜索DFS,只不过数据结构相对复杂一点,需要用到二维的vector,而且每当DFS搜索到新节点时,都要保存该节点。而且每当找出一条路径之后,都将这个保存为一维vector的路径保存到最终结果二位vector中。并且,每当DFS搜索到子节点,发现不是路径和时,返回上一个结点时,需要把该节点从一维vector中移除。代码如下:
class Solution { public: vector<vector<int> > pathSum(TreeNode *root, int sum) { vector<vector<int>> res; vector<int> out; helper(root, sum, out, res); return res; } void helper(TreeNode* node, int sum, vector<int>& out, vector<vector<int>>& res) { if (!node) return; out.push_back(node->val); if (sum == node->val && !node->left && !node->right) { res.push_back(out); } helper(node->left, sum - node->val, out, res); helper(node->right, sum - node->val, out, res); out.pop_back(); } };
3.没必要从开始到叶子节点结束,任意路径和。
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 Return 3. The paths that sum to 8 are: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11
这道题让我们求二叉树的路径的和等于一个给定值,说明了这条路径不必要从根节点开始,可以是中间的任意一段,而且二叉树的节点值也是有正有负。那么我们可以用递归来做,相当于先序遍历二叉树,对于每一个节点都有记录了一条从根节点到当前节点到路径,同时用一个变量curSum记录路径节点总和,然后我们看curSum和sum是否相等,相等的话结果res加1,不等的话我们来继续查看子路径和有没有满足题意的,做法就是每次去掉一个节点,看路径和是否等于给定值,注意最后必须留一个节点,不能全去掉了,因为如果全去掉了,路径之和为0,而如果假如给定值刚好为0的话就会有问题,整体来说不算一道很难的题,参见代码如下:
class Solution { public: int pathSum(TreeNode* root, int sum) { int res = 0; vector<TreeNode*> out; helper(root, sum, 0, out, res); return res; } void helper(TreeNode* node, int sum, int curSum, vector<TreeNode*>& out, int& res) { if (!node) return; curSum += node->val; out.push_back(node); if (curSum == sum) ++res; int t = curSum; for (int i = 0; i < out.size() - 1; ++i) { t -= out[i]->val; if (t == sum) ++res; } helper(node->left, sum, curSum, out, res); helper(node->right, sum, curSum, out, res); out.pop_back(); } };
-
【leetcode 二叉树路径和】Path Sum 和 Path Sum II
2014-11-19 00:17:09Path Sum 1、题目 fenPath Sum
1、题目
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree andsum = 22
,5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
return true, as there exist a root-to-leaf path
5->4->11->2
which sum is 22.2、分析
这道题很简单,用递归代码一目了然3、代码
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool hasPathSum(TreeNode *root, int sum) { if(!root) return false; //空树,返回false if(!root->left && !root->right) return root->val==sum; //左右子树均为空,判断val是否等于sum return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val); //递归调用hasPathSum函数 } };
Path Sum II
1、题目
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree andsum = 22
,5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
return
[ [5,4,11,2], [5,8,4,5] ]
2、分析
递归法,对递归函数执行的逻辑要理清,画图模拟一遍有帮助于理解程序的执行流程3、代码
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int> > pathSum(TreeNode *root, int sum) { vector< vector<int> > result; vector<int> current; pathSum(root,sum,current,result); return result; } private: void pathSum(TreeNode *root,int sum,vector<int> current,vector<vector<int>> &result) //必须用引用&,否则传递过来的只是current、result的副本,函数递归调用结束后,这些副本在栈里面被释放掉,并未真正改变current、result { if(!root) return; current.push_back(root->val); if(!root->left && !root->right) { if(sum==root->val) result.push_back(current); } pathSum(root->left,sum-root->val,current,result); pathSum(root->right,sum-root->val,current,result); current.pop_back(); //pop掉容器最后一个元素 } };
-
leetcode二叉树 找路径_leetcode二叉树的路径和,LeetCode
2021-01-12 22:54:18找出路径和等于给定数值的路径总数。路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。...记录第一篇博客,养成好习惯
题目描述
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
示例:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/
5 -3
/ \
3 2 11
/ \
3 -2 1
返回 3。和等于 8 的路径有:
5 -> 3
5 -> 2 -> 1
-3 -> 11
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/path-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
思路
1.在题干的描述中难点在于
路径不需要从根节点开始,也不需要在叶子节点结束
1)不妨先考虑路径必须要从根节点开始再到叶节点结束,记录路径中满足sum的路径和,这就会构成第一层递归
此时
遍历
在叶节点结束,但构成sum的
路径
不一定结束在叶节点
2)将每个遍历到的节点都看作根节点,则构成第二层递归
此时每个遍历到的节点,则会实现不一定从根节点出发
代码(Python实现)
class Solution(object):
#第一层递归,类似于树的中序遍历
#实现:让遍历到的每个节点,依次作为根节点
def pathSum(self, root, sum):
pathNum=0
if root!=None and root.val!=None:
pathNum=pathNum+self.fun(root,sum)
pathNum=pathNum+self.pathSum(root.left,sum)
pathNum=pathNum+self.pathSum(root.right,sum)
return pathNum
#第二层递归
#实现:找出从root节点出发到叶节点过程中,和为tempSum的路径总和
#(注意此处的tempSum与题干中要求的sum并不相同)
def fun(self,root,tempSum):
pathNum=0
if root!=None:
tempSum=tempSum-root.val
if tempSum==0:
#此时可能还未到达叶节点
pathNum=pathNum+1
pathNum=pathNum+
self.fun(root.left,tempSum)+
self.fun(root.right,tempSum)
return pathNum
-
Leetcode 二叉树路径
2020-05-28 10:53:07给定一个二叉树和一个值sum,判断是否有从根节点到叶子节点的节点值之和等于sum的路径, 例如: 给出如下的二叉树,sum=22, 5↵ / ↵ 4 8↵ / / ↵ 11 13 4↵ / / ↵ 7 2 5 1 返回true,因为存在一条路径5-&... -
leetcode二叉树 找路径_Leetcode 二叉树中的最大路径和(hard)-JavaScript 解法
2021-01-03 18:24:27题目给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1,2,3] 1 / 2 3 输出: 6 ... -
leetcode二叉树 找路径_LeetCode124二叉树中的最大路径和
2020-12-30 15:18:16这道题和LeetCode687最长同值路径和LeetCode543二叉树的直径很相似,都很难,每个题都做了很久三道题的共性是dfs函数并非直接实现了目标功能,而是将目标功能拆解,实现目标功能的一部分,然后再利用某种关系(根节点... -
LeetCode 二叉树路径问题 Path SUM(①②③)总结
2017-08-14 12:08:13(尊重劳动成果,转载请...题目大意是这个意思,给定一棵二叉树和一个sum值,判断树中是否存在一条从根节点到叶子节点的路径,使得路径上的值加起来刚好等于sum。 解题思路: 递归结束条件: root == null返回fal... -
leetcode二叉树 找路径_LeetCode实战:二叉树中的最大路径和
2020-12-21 07:19:08原标题:LeetCode实战:二叉树中的最大路径和 背景题目英文Given a non-empty binary tree, find the maximum path sum.For this problem, a path is defined as any sequence of nodes from some starting node to ... -
leetcode二叉树 找路径_十行代码说清楚:leetcode 二叉树中和为某一值的路径
2021-01-03 18:24:24二叉树中和为某一值的路径除了逻辑上的考虑之外,本题还需要注意深拷贝和浅拷贝的问题。在把找到的结果追加到数组中时,需要通过 list() 函数将中间遍历得到的 path 进行深拷贝这样,在退出 dfs 函数时,path 中的... -
leetcode二叉树 找路径_LeetCode-124 二叉树中的最大路径和
2021-01-03 18:24:39题目:给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定 经过根节点。解法一:递归法(双层递归) 首先说下,递归法的... -
leetcode二叉树 找路径_LeetCode刷题实战124:二叉树中的最大路径和
2021-01-03 18:24:36算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务...今天和大家聊的问题叫做二叉树中的最大路径和,我们先来看题面:https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/Given a ... -
leetcode二叉树 找路径_LeetCode(124. 二叉树中的最大路径和) 题解
2021-01-03 18:24:28124. 二叉树中的最大路径和题目给定一个非空二叉树,返回其最大路径和。本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。思路题意:从树中任意一个... -
LeetCode 二叉树的路径遍历
2018-10-28 15:59:45给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 示例: 给定如下二叉树,以及目标和 sum = 22, 5 / \ 4 8 / / \ 11 13 4 ... -
LeetCode 二叉树中的路径和问题、二叉树的所有路径
2020-05-04 08:27:37给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树,以及目标和 sum = 22, 5 / \ 4... -
leetcode二叉树的最大路径和
2019-09-24 22:43:54给定一个非空二叉树,返回其最大路径和。本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。 该路径至少包含一个节点,且不一定经过根节点。 def_init_(self): self.result=float("-inf") ... -
leetcode:二叉树路径和
2020-03-26 12:45:43注意,路径不一定非得从二叉树的根节点或叶节点开始或结束,但是其方向必须向下(只能从父节点指向子节点方向)。 审题: 题目中的重点包括如下: 节点值或正或负 路径可从任意节点开始 路径只能沿父节点到子节点 ... -
LeetCode 二叉树中的最大路径和
2019-02-21 20:44:09给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1,2,3] 1 / \ 2 3 输出: 6 示例 2: ... -
Leetcode 二叉树最大内部路径长度
2020-05-21 10:52:56给定一个二叉树,请计算节点值之和最大的路径的节点值之和是多少。 这个路径的开始节点和结束节点可以是二叉树中的任意节点 例如: 给出以下的二叉树, 1↵ / ↵ 2 3 返回的结果为6 思路:和最长连续子... -
leetcode二叉树 找路径_【文末福利】每日一道 LeetCode (26):路径总和
2021-01-03 18:24:26❝每天 3 分钟,走上算法的逆袭之路。❞前文合集每日一道 LeetCode 前文合集代码仓库GitHub:...希望各位以后能多点再看和转发,让我恰... -
LeetCode二叉树中的最大路径和 C语言
2019-07-19 22:39:51思路 一开始没有什么思路,看了大家的评论之后大概了解了可以用递归算的方法,最关键的就是有一个变量sum记录最大路径(加上...max_left,max_right标记新的根结点加上以被选择的最长的左子树和右子树的路径,left_ga... -
leetcode二叉树
2019-05-25 17:41:21给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left ... -
leetcode二叉树 找路径_二叉树:总结篇!(需要掌握的二叉树技能都在这里了)...
2021-01-03 18:24:25❞不知不觉二叉树已经和我们度过了「三十三天」,代码随想录里已经发了「三十三篇二叉树的文章」,详细讲解了「30+二叉树经典题目」,一直坚持下来的录友们一定会二叉树有深刻理解了。在每一道二叉树的题目中,我都...
-
MHA 高可用 MySQL 架构与 Altas 读写分离
-
MySQL 事务和锁
-
大数据开发之Hadoop学习7--HDFS客户端操作
-
BGLightChangeDLL.zip
-
Zabbix自定义项
-
智能停车场云平台(附vue+SpringBoot前后端项目源码)
-
应届生与IT培训生,就业谁更占优势?
-
2019年-华启学院中级通信工程师综合能力真题及答案(完整版).pdf
-
机器学习可视化软件机器学习可视化软件
-
MySQL 性能优化(思路拓展及实操)
-
微服务运行在docker上
-
智慧路灯杆云盒网关的功能和应用
-
【爱码农】C#制作MDI文本编辑器
-
com.termux_102.apk
-
Epplus的出坑笔记
-
JS: map 和 weakMap
-
Java集合类自我总结
-
计算机复试英语准备.pdf
-
C++代码规范和Doxygen根据注释自动生成手册
-
使用 Linux 平台充当 Router 路由器