一亩三分地

 找回密码 注册账号

扫描二维码登录本站


北美版丁香园
美国和加拿大
疫情地图实时动态追踪

热门职场讲座
Career in Tech
职场晋升之路

Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 593|回复: 6
收起左侧

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

[复制链接] |试试Instant~ |leetcode, 刷题
我的人缘0

分享帖子到朋友圈
akdhfikbk | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (274)
 
 
1% (3)    👎

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

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

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问题,递归和循时环的本质,基本通用循环模板
我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
不知道什么叫函数的物理意义,不过看起来pathSum函数相当于在递归枚举路径的起点,然后调用findPath寻找以当前节点为起点的符合条件的路径并统计个数。这是lz想问的吗?

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

使用道具 举报

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

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

使用道具 举报

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

如果合并两个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 这个好厉害

查看全部评分

回复

使用道具 举报

我的人缘0
本楼: 👍   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)就找到了一个合法的终点,因为确定了起点和终点,在树上的路径是唯一的,所以也就确定了路径,可以把这个结果累加上去。
回复

使用道具 举报

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

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

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

使用道具 举报

我的人缘0
qwseda123 2020-1-24 12:09:08 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (124)
 
 
3% (5)    👎
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://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-4-4 13:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表