登录
注册
关注
TOP

查看: 806|回复: 6
收起左侧

[Leetcode] Tree的recursion还是逻辑不清-Lc437 Path Sum III

[复制链接] |只看干货 |leetcode, 刷题

升级   1.7%


分享帖子到朋友圈
akdhfikbk | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (887)
 
 
5% (48)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
正在练习那个嵌套recusion的问题,搞不清两个function的物理意义是什么这是我的代码:

[Java] 纯文本查看 复制代码
 public int pathSum(TreeNode root, int sum) {
        if(root==null) return 0;
        
        //root+left+right
	//this is wrong answer
        //return findPath(root, sum)+findPath(root.left, sum)+findPath(root.right,sum);
	return findPath(root, sum)+pathSum(root.left, sum)+pathSum(root.right,sum);
    }
    
    private int findPath(TreeNode root, int sum){
        //base case
        if(root==null) return 0; 
        int counter=0;
        sum=sum-root.val;
        if(sum==0) counter ++;
        return counter + findPath(root.left, sum)+findPath(root.right,sum);
        }



目前我的理解是:

findPath是 每次从头节点出发,count path路径次数;

pathSum是 让每一个节点都是新的头节点;
我主要对于pathSum这个function的物理意义有疑问,不清楚其作用,如果不考虑findPath程序没被调用的问题,我这样的表达式的物理意义也没问题啊:
[Java] 纯文本查看 复制代码
pathSum(root, sum)+pathSum(root.left, sum)+pathSum(root.right,sum)


这样写的唯一问题就是findPath function没被调用,不过真要return这样的话,可以改动下findPath在pathSum中的位置实现吗?




上一篇:hard题要做到什么程度?
下一篇:【刷题思考】刷题新手,解决差1问题,递归和循时环的本质,基本通用循环模板

升级   82.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
不知道什么叫函数的物理意义,不过看起来pathSum函数相当于在递归枚举路径的起点,然后调用findPath寻找以当前节点为起点的符合条件的路径并统计个数。这是lz想问的吗?

另外第二种写法没调用findPath不是唯一的问题,看起来这样做会死循环。
回复

使用道具 举报

升级   1.7%

 楼主| akdhfikbk 2020-1-24 03:04:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (887)
 
 
5% (48)    👎
jsnjwty 发表于 2020-1-24 02:20
不知道什么叫函数的物理意义,不过看起来pathSum函数相当于在递归枚举路径的起点,然后调用findPath寻找以 ...

就是各自function的作用是什么.....
能再详细一点吗,
btw枚举是什么意思
回复

使用道具 举报

升级   48.43%

qwseda123 2020-1-24 06:16:34 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (2029)
 
 
2% (51)    👎
楼主的思路没错 但是你的思路实现的具体方式 就是你贴出来的正确代码

如果合并两个function到一起 在不改变签名的情况下 那就不能button up 向上传递两个信息  

[Bash shell] 纯文本查看 复制代码
class Solution {
    public int pathSum(TreeNode root, int sum) {
        //base case
        if (root == null) return 0;
        //write a method to calculate current node path sum
        int node = findPath(root,sum);
        //botton up
        int left = pathSum(root.left, sum);
        int right = pathSum(root.right, sum);
        int res = node + left + right;
        return res;
   }
   private int findPath(TreeNode root, int sum){
       //base case
       if (root == null) return 0; 
       int counter = 0;
       sum = sum-root.val;
       if (sum==0) counter ++;
       //another botton up
       int left = findPath(root.left, sum);
       int right = findPath(root.right, sum);
       
       return counter + left + right;
    }
}

评分

参与人数 1大米 +2 收起 理由
akdhfikbk + 2 这个好厉害

查看全部评分

回复

使用道具 举报

升级   82.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
akdhfikbk 发表于 2020/01/24 03:04:52
就是各自function的作用是什么.....
能再详细一点吗,
btw枚举是什么意思
枚举就是穷举?Enumerate?简单来说这里就是尝试每一个节点作为起点的情况。

我都有点晕了,lz是自己写出来的程序自己看不懂吗😂

sumPath本质是递归遍历整个树,对于遍历到的每个节点调用findPath来统计以当前节点为起点的符合要求的路径。findPath事实上是遍历了以findPath遍历到的节点为根的整个子树,一边遍历一边记录从子树的根节点到当前节点的路径和(这里的实现方式是要求的sum-路径和)。如果和是要求的(sum-currentValue==0)就找到了一个合法的终点,因为确定了起点和终点,在树上的路径是唯一的,所以也就确定了路径,可以把这个结果累加上去。
回复

使用道具 举报

升级   1.7%

 楼主| akdhfikbk 2020-1-24 11:44:49 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (887)
 
 
5% (48)    👎
qwseda123 发表于 2020-1-24 06:16
楼主的思路没错 但是你的思路实现的具体方式 就是你贴出来的正确代码

如果合并两个function到一起 在不 ...

这个写法好清晰明了,
楼主主要不懂的是为啥上面的就recursively call 自己,下面也只recursively call自己
两个function的具体逻辑意义是什么...
回复

使用道具 举报

升级   48.43%

qwseda123 2020-1-24 12:09:08 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (2029)
 
 
2% (51)    👎
akdhfikbk 发表于 2020-1-24 11:44
这个写法好清晰明了,
楼主主要不懂的是为啥上面的就recursively call 自己,下面也只recursively call ...

问题1: 给你一个tree 让你算只能从root开始,到任意node(不一定是叶子节点)的path sum,写个method。
follow up: 用上面的method 来算整一棵树 从任意node开始 到任何node 的path sum
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

论坛导航
快速回复 返回顶部 返回列表