一亩三分地论坛

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

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

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

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-7-6 20:51:54 | 显示全部楼层 |阅读模式

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

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

x
4.1 Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.

回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。



grassgigi 发表于 2014-7-6 23:35:04 | 显示全部楼层
【解题思路】
Recursion.

自己写的时候return了一个boolean值(表示subtree是否balance)和int值(height of the subtree)
书上的答案return -1如果subtree is not balance, 省下了boolean的空间

【时间复杂度】
O(N) - N is # of tree nodes

【空间复杂度】
O(N)

【gist link】
https://gist.github.com/chrislukkk/6581e137e1ad9673a973
BinaryTree: https://gist.github.com/chrislukkk/2a1f825b8e924ea773e8

【test case】
A binary tree builder: Building a tree based on itspreorder and inorder sequence
https://gist.github.com/chrislukkk/2a1f825b8e924ea773e8
回复 支持 反对

使用道具 举报

donnice 发表于 2014-7-7 07:39:46 | 显示全部楼层
【解题思路】
参考了网上的思路,用递归遍历每一个点,并计算其左右树的高度差。凡是有超过1的就说明不平衡
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://github.com/donnice/donnice/blob/master/Q4_1
【Test】
例子里我用的树分别是:
              5                                                                7
            2                  8                                            2                     8
      1          4       7                                          1             4      
            3                                                                3            5
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-7-7 11:26:03 | 显示全部楼层
本帖最后由 chouclee 于 2014-7-7 11:30 编辑

【解题思路】
递归遍历每一个点,计算左右两个subtree的高度差
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/chouclee/dac2df817f826f5df3a4
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】    /*                            7
                         *                         /    \
                         *                     /         \
                         *                  4            9
                         *                 / \         / \
                         *              2   5     8   10
                         *            / \    \            \
                         *         1   3    6          11
                         *        /
                        *       0
                 */  




补充内容 (2014-7-9 12:54):
gist link贴错了。。。囧 https://gist.github.com/chouclee/5a7bdbed1ab1c8b3d150
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-8 12:24:31 | 显示全部楼层
【解题思路】
参考书后解答=。=
【时间复杂度】
O(N)
【空间复杂度】
O(H)
【gist link】
https://gist.github.com/e448a924ba7d3b4d0f8b
【test case】
BST:
5 3 4 1 2 6  -> false
5 3 4 1 2 6 8 -> true
5 3 4 1 2 6 8 1 -> false
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-7-9 00:12:13 | 显示全部楼层
【解题思路】Ref to the book... count the left height and right height of each node, also copy the tree structure from lss
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/bitcpf/26394ee53639cdbf721f
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-7-9 01:09:07 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-7-9 14:26:07 | 显示全部楼层
【解题思路】Return the current height for helper() function. Return -1 if the tree is not balanced.
【时间复杂度】O(N)
【空间复杂度】O(H)
【gist link】https://gist.github.com/jason51122/ec57311f8d1fcd8e9e41
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-7-10 05:45:56 | 显示全部楼层
【解题思路】recurse through the entire tree, compute the height of each subtree
【时间复杂度】o(n^2)
【空间复杂度】o(n)
【gist link】https://gist.github.com/hilda8519/24a6435951a05ac1b8de

答案的第二个例子不错
回复 支持 反对

使用道具 举报

Neal 发表于 2014-7-10 07:32:14 | 显示全部楼层
【解题思路】transverse the tree recursively, examine each node and check if two subtrees are balanced.
【时间复杂度】o(n)
【空间复杂度】o(max(height))
【gist link】https://gist.github.com/nealhu/091a742d6c11d5298760
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-7-11 22:00:03 | 显示全部楼层
【解题思路】
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

查看全部评分

回复 支持 反对

使用道具 举报

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
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 12:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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