12
返回列表 发新帖
楼主: wrj5518
跳转到指定楼层
上一主题 下一主题
收起左侧

[CareerCup] 【第三轮】7.7-7.13 CareerCup 4.1

全局:
【解题思路】
Compute the height of each sub-tree while checking whether the sub-tree is balanced or not


【时间复杂度】
O(n) (n is the number of nodes)

【空间复杂度】
O(h) (h is the height of tree)


【gist link】
https://gist.github.com/happyWinner/ab96e6406d587547756c

评分

参与人数 1大米 +2 收起 理由
kimiflasky + 2 回答的很好!

查看全部评分

回复

使用道具 举报

🔗
qianhuang 2014-7-12 09:47:12 | 只看该作者
全局:
【解题思路】
recursion method. each time we compute length(b->lchild) and length(b->rchild). But in this way, we compute length duplicately. Runtime is O(n^2), space is O(H), H is tree height.
To optimize it, we can check balance in length computating.
【时间复杂度】
O(n)
【空间复杂度】
O(H)
【gist link】
https://gist.github.com/qianhuang/6abaee1a1c8599edca97
回复

使用道具 举报

🔗
兰橘清檬 2014-7-13 02:14:11 | 只看该作者
全局:
方法一:
【解题思路】
递归,写一个计算节点 height 的函数
【时间复杂度】
O (N log (N)) -- N : 总节点数
【空间复杂度】
O( ? )
【gist link】
https://gist.github.com/JoyceeLee/5a6141e1afb69bcd3295

方法二:
【解题思路】
在 getHeight 里同时进行 balance 检查
【时间复杂度】
O (N) -- N : 总节点数
【空间复杂度】
O( H )
【gist link】
https://gist.github.com/JoyceeLee/5a6141e1afb69bcd3295
回复

使用道具 举报

🔗
jyh橘子 2014-7-13 15:35:53 | 只看该作者
全局:
【解题思路】 recursive solutions. check if left subtree balanced, if right subtree balanced and if the height difference is less than one.    return the height and use -1 to indicate the subtree is not balanced.
【时间复杂度】
O(N)
【空间复杂度】
O(H)
【gist link】https://gist.github.com/jyhjuzi/99e67e68e726427da58c
回复

使用道具 举报

🔗
wilbert 2014-7-14 01:33:47 | 只看该作者
全局:
【解题思路】
Compute the height of the two subtree while comparing if the subtree is balanced or not. return -1 for height to indicate not balanced.
【时间复杂度】
O(N)
【空间复杂度】
O(H)
【gist link】
https://gist.github.com/iwilbert/bb5372cf358ff1981548
回复

使用道具 举报

🔗
renli3000 2014-7-18 02:45:50 | 只看该作者
全局:
【解题思路】
参考了答案的思路,一起检查height和balance,自己智商捉鸡了...
【时间复杂度】
O(N)
【空间复杂度】
O(H)
【gist link】
https://gist.github.com/Noahsark/da4873bb3831d8ea8c65
回复

使用道具 举报

🔗
tonygxxx1212 2014-7-19 21:59:20 | 只看该作者
全局:
【解题思路】height() + check()
【时间复杂度】
O (n)
【空间复杂度】
O(h)
【gist link】
https://gist.github.com/xun-gong/ce771c4af3f039a35bef
回复

使用道具 举报

🔗
heycinderella 2014-10-23 03:17:59 | 只看该作者
全局:
leetcode也有一样的 Balanced Binary Tree,想了老半天DFS啥啥什么顺序啥啥,结果重点应该在checkBalanced的时候一旦不balance就返回-1
【解题思路】参考了书上的答案,getHeight and check ifBalanced at the same time
【时间复杂度】
O (n)
【空间复杂度】
O(lgN)
【gist link】
https://gist.github.com/XiaoxiaoLi/c013c43b64b602be0013
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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