一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1488|回复: 20
收起左侧

[树/链表/图] 一遇到Tree的问题就抓瞎啊,求问有没有什么理解的窍门……

[复制链接] |试试Instant~ |关注本帖
coldfire8 发表于 2016-2-19 17:44:26 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
LC上tree tag的题目,除了那些可以用简单的递归解的,稍微复杂一点就完全没思路啊!!!完全没思路!!!
比如什么验证preorder之类的,根本想不到要去怎么验证。。。
基本的思路都没有,而且就算有思路,也很难把感性的思路转化为程序语言,比如while啊,DFS之类的
而且大部分题做了一两遍,觉得自己真的理解了,过两天竟然又忘了。。我这样的是不是根本不适合写代码啊啊啊

求问各位大神我这样的可能是哪里出了问题?有没有什么好的训练方法?
sapphire0315 发表于 2016-2-19 23:56:48 | 显示全部楼层
每道题目 应该画recursion tree
回复 支持 2 反对 0

使用道具 举报

justin 发表于 2016-2-20 00:06:16 | 显示全部楼层
同意楼上的。
关于树的题目,最好都是能画出来。
很多时候,只要你能画出recursion tree,那时间复杂度,树的遍历顺序,DP的结构,等等等等,就基本一目了然了。
回复 支持 1 反对 0

使用道具 举报

sapphire0315 发表于 2016-2-22 12:18:36 | 显示全部楼层
蛀牙jj 发表于 2016-2-22 07:41
recursion tree是指的这个吗?

不是呀 就是每一步参数怎么传的,返回值是啥
回复 支持 1 反对 0

使用道具 举报

 楼主| coldfire8 发表于 2016-2-20 09:17:05 | 显示全部楼层
sapphire0315 发表于 2016-2-19 23:56
每道题目 应该画recursion tree

谢谢建议!我都还不知道~~T.T~~
回复 支持 反对

使用道具 举报

 楼主| coldfire8 发表于 2016-2-20 09:17:14 | 显示全部楼层
justin 发表于 2016-2-20 00:06
同意楼上的。
关于树的题目,最好都是能画出来。
很多时候,只要你能画出recursion tree,那时间复杂度, ...

感谢建议!
回复 支持 反对

使用道具 举报

sapphire0315 发表于 2016-2-20 09:50:33 | 显示全部楼层
coldfire8 发表于 2016-2-20 09:17
谢谢建议!我都还不知道~~T.T~~

用least common ancestor 写写
回复 支持 反对

使用道具 举报

 楼主| coldfire8 发表于 2016-2-20 10:18:55 | 显示全部楼层
sapphire0315 发表于 2016-2-20 09:50
用least common ancestor 写写

啊啊啊……那就是我头疼的题之一……我突然发现我不知道你说的recursion tree代表什么,是DFS的时候每一步的状态吗?
回复 支持 反对

使用道具 举报

sapphire0315 发表于 2016-2-20 16:25:56 | 显示全部楼层
coldfire8 发表于 2016-2-20 10:18
啊啊啊……那就是我头疼的题之一……我突然发现我不知道你说的recursion tree代表什么,是DFS的时候每一 ...

你给我发email吧 michard.su2015@gmail.com
回复 支持 反对

使用道具 举报

mchzh 发表于 2016-2-20 16:44:37 | 显示全部楼层
tree的问题上来先用divide&conquer去考虑,先分后治
回复 支持 反对

使用道具 举报

pepero 发表于 2016-2-22 07:00:46 | 显示全部楼层
recursion tree? 我只知道已知递推公式,分析复杂度的时候用递归树,如果一道题没什么思路,怎么用递归树解呢?sapphire0315 能不能举个例子,讲讲用法, 比方说怎么用递归树求解lca问题。谢谢
回复 支持 反对

使用道具 举报

蛀牙jj 发表于 2016-2-22 07:41:20 | 显示全部楼层
sapphire0315 发表于 2016-2-19 23:56
每道题目 应该画recursion tree


                               
登录/注册后可看大图

recursion tree是指的这个吗?

回复 支持 反对

使用道具 举报

iwofr 发表于 2016-2-22 12:50:28 | 显示全部楼层
tree的题出了BFS大部分都需要递归,我遇tree题先想用递归咋做,其实用递归一般code都会非常简单
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2016-2-22 13:00:52 | 显示全部楼层
递归的状态空间处理和 dfs 非常像,lz 有空多做做 tree 上的 dfs 题多画出来就好理解了。 搜索时候的 backtracking 其实也一样。
回复 支持 反对

使用道具 举报

desperate500 发表于 2016-2-22 13:21:57 | 显示全部楼层
分治法 + 三方合并 基本见一个秒一个
回复 支持 反对

使用道具 举报

蛀牙jj 发表于 2016-2-23 01:30:17 | 显示全部楼层
sapphire0315 发表于 2016-2-22 12:18
不是呀 就是每一步参数怎么传的,返回值是啥

可以贴个例子吗?
比如leetcode 上 4. Median of Two Sorted Arrays
https://leetcode.com/problems/median-of-two-sorted-arrays/
应该怎么画recursion tree呢?
谢谢
回复 支持 反对

使用道具 举报

aangel 发表于 2016-2-23 07:30:54 | 显示全部楼层
desperate500 发表于 2016-2-22 13:21
分治法 + 三方合并 基本见一个秒一个

请问你说的三方合并指什么啊?
回复 支持 反对

使用道具 举报

angelamissgao 发表于 2016-2-23 07:45:31 | 显示全部楼层
最不喜欢什么tree有的时候会走到null~
回复 支持 反对

使用道具 举报

desperate500 发表于 2016-2-23 09:38:02 | 显示全部楼层
aangel 发表于 2016-2-23 07:30
请问你说的三方合并指什么啊?

大概就是 本层满足条件 + 左边有效 + 右边有效
回复 支持 反对

使用道具 举报

techno 发表于 2016-2-23 11:18:05 | 显示全部楼层
也是刚开始刷leetcode,从tree开始,我怎么感觉越来越有感觉呢。嗯,画图是个好方法,三方合并是啥?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 16:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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