-
2021-09-07 22:04:31
给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [1,2,3,null,5]
输出:[“1->2->5”,“1->3”]
示例 2:输入:root = [1]
输出:[“1”]提示:
树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-paths
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> paths = new ArrayList<>(); getPath(root,"",paths); return paths; } void getPath(TreeNode root,String path,List<String> paths){ if(root != null){ StringBuffer sb = new StringBuffer(path); sb.append(Integer.toString(root.val));//将根节点加入 //向下遍历左右子树 if(root.left == null && root.right == null){ //当前是叶子节点 paths.add(sb.toString());//将路径添加到结果集中 }else{ //不是叶子节点,继续向下遍历 sb.append("->"); getPath(root.left,sb.toString(),paths); getPath(root.right,sb.toString(),paths); } } } }
更多相关内容 -
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二叉树路径总和
2022-03-09 19:26:04路径之和 LeetCode题目来源 1.1 题目描述 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,...路径之和
1.1 题目描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。叶子节点 是指没有子节点的节点。
1.2 示例
2.1 解题
解题方法:递归进行计算
二叉树从上向下进行递归计算,每遍历一个节点,就用target-root.val。当叶子节点值等于最后一次target-root.val,则存在路径。Java版解题
class Solution { public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } if (root.left == null && root.right == null) {//遍历到叶子节点时,判断最后的target减去前面路径消耗的val等于节点的val return sum == root.val; } return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);//多条路径遍历二叉树 } }
解题结果
-
LeetCode二叉树中的最大路径和
2021-12-31 23:17:17124. 二叉树中的最大路径和 路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点,且不一定经过根节点。 路径和是...路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ,返回其 最大路径和 。
示例 1:
输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6
示例 2:
输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42
思路:
这道题是一个困难题。因为它确实不像传统二叉树的方法,简单写一下递归就可以得到结果。无法单单用递归解决的原因在于在一棵二叉树里画的路径可以是各种各样的——可以直接从根节点沿着一条路线画到子节点;也可以从某个子节点起,往上行走至某中间节点,再下落到另一个子节点上……可见,我们的路径可以是各种各样,尤其是题目中的节点还有负数的情况,这也让整个问题看起来十分复杂。
首先说明,下面的题解会写的很“勉强”(这也是我自己写的比较别扭的一篇思路了),所以千万不要钻牛角尖。我还是建议一半理解+一半记忆。
虽然我们可能的“最大路径”多种多样,但我们总归可以将他们分成两类:可以用递归寻找(“竖着”的路径) 以及 不可以用递归寻找(“横着”的路径)。
对于前者,我们就照常使用我们平时解决二叉树的方法去写递归;对于后者,我们开设一个全局变量来实时更新存储。最终我们将两类的总结果进行比较,得到最大值。
具体来看,我们把问题缩小,一个大二叉树,我们想象成一棵棵只有根、左节点、右节点的小树。这一棵棵的小树构成大树,我们只需要考虑小树即可。按照题意:一颗三个节点的小树的结果只可能有如下6种情况:
根 + 左 + 右
根 + 左
根 + 右
根
左
右
要看能否进行递归寻找,就要看能否从根节点向下延伸。
其中可以递归查找的情况有:根 + 左,根 + 右,根这三种,可以想象成拿着笔从根出发,最起码可以向左向右走或者不动,起码可以保持路径是“竖着”的。可以发现一定要包含根节点,这样我们定义递归函数的时候,就是传入一个节点,传出以传入节点为根节点的最大路径。
而不可以递归查找的情况有:左,右,根+左+右这三种,对于只有左或者右的情况,我们都无法碰到根节点,自然无法递归延伸;对于根,左,右都存在的情况,明显是一个“横着”的路径,所以也是无法通过延伸递归来获得的。
好了,点到为止!就算没有完全看懂思路也没关系,我们直接看代码!很好理解和记忆:
代码:
#先把情况列到最上面作为参考 # 根 + 左 + 右 # 根 + 左 # 根 + 右 # 根 # 左 # 右 class Solution(object): def maxPathSum(self, root): no_di=[float('-inf')]#no_di存放非递归最大 def di(root):#di返回以root为根节点的最大路径 if not root:#老递归了,定义base case return float('-inf') #因为节点值有负的 所以用负无穷 不能用0 right = di(root.right)#获得以它右节点为根节点的最大路径 left = di(root.left)#获得以它左节点为根节点的最大路径 #左,右,根+左+右 no_di[0] = max(no_di[0],root.val+right+left,right,left)#非递归 #根,根+左,根+右 di_=max(root.val,root.val+left,root.val+right) # di_存放递归最大 return di_ new_max=di(root)#不能把这个di(root)直接放到下面的return #因为di函数里要修改no_di[0],所以他要先执行 return max(no_di[0],new_max)
小结:
我们单看递归的部分(不去管no_di即非递归相关),可以发现函数di(root)的功能就是传入节点root,计算其左节点的最大路径和右节点的最大路径,然后计算max(自身值,自身值+左,自身值+右)作为di(root)的返回值。这样子就可以完美的计算出“竖直”方向上的最大路径了。
而“横着”的路径,则在每次递归函数中尝试与全局变量进行更新,比较巧妙地放在了递归函数里。
代码中要注意因为我们的节点有负数的情况,因此初始化最大值要用负无穷float(‘-inf’)而不是0。此外,存放非递归最大的变量no_di我用的一个列表来存放,这样可以充当全局变量的作用,否则在leetcode里面可能会找不到该变量,算是一个小技巧,之前也提到过。
……
2021年的最后一个小时,留个记录,祝岁月静好,国泰民安~
-
【LeetCode】二叉树最大路径和(dfs)
2022-04-08 06:10:17二叉树最大路径和 题目链接:https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/ 分析: 这个题目是求二叉树的最大路径和,要点有两个: 最大不能走回头路:从根节点延伸的路径,你不能走了左子树又... -
Leetcode257二叉树所有路径及路径和
2020-12-12 15:19:13文章目录题目一:二叉树所有路径分析代码变形: 所有路径和题目描述分析代码结果参考资料 题目一:二叉树所有路径 /** * ClassName: LeetCode257SumTree <br/> Function: <br/> * * 给定一个... -
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
-
【LeetCode】二叉树的路径问题(所有路径,路径之和)
2020-10-06 16:03:04路径问题涉及回溯 回溯一般和递归捆绑在一起 一般递归函数为void型 ...一个栈用来模拟递归用来存放和当前结点对应的已经遍历的路径; 同时pop更新,同时压入栈(结点,当前路径(注意会改变变量的情况,设置. -
Python Leetcode二叉树求解最长路径问题
2021-07-29 12:22:22某公司的机试,给定一棵树,一个目标值,求从根节点到叶子节点和为目标值的最长序列长度or路径。...# 二叉树:求指定目标和下的最长的序列长度 from collections import defaultdict m, targetNum = map(int, inp -
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
2021-01-12 22:54:18找出路径和等于给定数值的路径总数。路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。... -
leetcode-二叉树中的最大路径和
2019-09-19 15:58:45给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点 图中划红线的表示路径,此题中要寻找的路径必须是能够... -
leetcode二叉树专题---C++实现
2022-04-14 14:18:44二叉树的所有路径 222. 完全二叉树的节点个数 222. 完全二叉树的节点个数 给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。 完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每... -
LeetCode—二叉树最短路径
2020-04-19 16:36:33leetcode-Minimum Depth of Binary Tree Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf n... -
LeetCode之二叉树中的最大路径和
2020-06-21 15:59:25求二叉树的最大路径和,即求以每个节点为根节点的二叉树的最大路径和,再取其中的最大值 最大路径和可以通过:root->val + 左子节点最大贡献 + 右子节点最大贡献 通过一个变量maxSum随时更新最大路径和 接... -
LeetCode:二叉树的所有路径
2018-08-18 11:23:14给定一个二叉树,返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 输入: 1 / \ 2 3 \ 5 输出: ["1->2->5", "1->3"] 解释: ... -
【leetcode 二叉树路径和】Path Sum 和 Path Sum II
2014-11-19 00:17:09Path Sum 1、题目 fen -
LeetCode 二叉树的直径
2020-12-22 05:06:45一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 注意:两结点之间的路径长度是... -
leetcode—二叉树中的最大路径和
2021-01-18 20:01:01当前节点的最大路径和 //要注意区分这两个值的含义,例如示例1: //节点1所能向上提供的最大路径值要么是2->1这条路径要么是3->1这条路径,注意向上这个词 //而节点1的最大路径和肯定是左边的路径加右边的路径 ... -
LeetCode二叉树中和为某一值得路径
2021-06-02 20:08:44输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例: 给定如下二叉树,以及目标和 target = 22, 5 / \ 4 8 / / \ ... -
LeetCode–二叉树的所有路径
2021-03-13 06:18:16LeetCode–二叉树的所有路径博客说明文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢!介绍题目给定一个二叉树,返回所有从根节点到叶子节点的路径。... -
LeetCode二叉树问题全解析(上)
2022-03-07 15:29:11许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树,且有左右之... -
Leetcode 二叉树的所有路径
2020-02-06 14:48:53主要思想,递归遍历整棵二叉树,每遍历到一个节点,并把节点加入路径,判断是否为叶节点 1.是叶节点,就把当前这个路径添加到List里, 2.不是叶节点,就在当前路径后加“->”(这是因为题目有格式要求,如果没有... -
LeetCode 二叉树中的路径和问题:二叉树中的最大路径和、二叉树的所有路径、求根到叶子节点数字之和
2020-05-03 22:57:44给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树,以及目标和 sum = 22, 5 / \ 4... -
LeetCode —— 257. 二叉树的所有路径(Python)
2020-08-21 11:43:58(2)从根结点开始遍历二叉树,遍历到某一个结点时,如果当前结点不是叶子结点,在变量string中记录当前结点的信息,接着分别遍历当前结点的左子结点和右子结点; # Definition for a binary tree node. # class ... -
leetcode解题二叉树篇
2022-03-27 18:43:51在我们解题过程中二叉树有两种主要的形式:满二叉树和完全二叉树。 满二叉树 满二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。 如图所示: 这棵二叉树... -
leetcode二叉树的最大深度c++
2019-04-28 20:57:40二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 递归: class Solution { public: int maxDepth(TreeNode* root) { int maxdepth=0; if(root==NULL) { ...