一亩三分地论坛

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

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

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

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

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

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

x
4.5 Implement a function to check if a binary tree is a binary search tree.

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


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



grassgigi 发表于 2014-7-8 10:16:07 | 显示全部楼层
本帖最后由 grassgigi 于 2014-7-8 10:42 编辑

【解题思路】
BFS - perform a inorder traversing, keep tracking two consecutive visited nodes, if the current one's value is smaller than the previous one, return false since BST is monotonic increasing inorder.

【时间复杂度】
O(N)

【空间复杂度】
O(N)

【gist link】
https://gist.github.com/chrislukkk/24270f55880fa1060d53
binray tree & tree builder:
https://gist.github.com/chrislukkk/2a1f825b8e924ea773e8
回复 支持 2 反对 0

使用道具 举报

圆梦梦剧场 发表于 2014-7-12 00:03:18 | 显示全部楼层
【解题思路】
recursion: check from root to leaves, passing the left & right bound to every sub-call

【时间复杂度】
O(n)

【空间复杂度】
O(logn)

【gist link】
https://gist.github.com/happyWinner/7023673688565a1f402

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

donnice 发表于 2014-7-12 02:58:43 | 显示全部楼层
【解题思路】
遍历每个点,保证右支的点都大,左支的点都小
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist】
https://github.com/donnice/donnice/blob/master/Q4_5
回复 支持 反对

使用道具 举报

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

使用道具 举报

bitcpf 发表于 2014-7-13 08:28:48 | 显示全部楼层
【解题思路】BST each node, compare left to current, current to right. Ref to 2nd codes
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist】https://gist.github.com/bitcpf/2d94f8556e160d311d96
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-7-13 09:29:07 | 显示全部楼层
【解题思路】
recursion with min and max limitation
【时间复杂度】
O(N)
【空间复杂度】
O(log N)
【gist】
https://gist.github.com/JoyceeLee/afb2727dc92838e881be
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-13 10:11:37 | 显示全部楼层
【解题思路】
1. left.data < curr.data < right.data, recursively check left and right child (WRONG!!! NOT SUFFICIENT CONDITION!!!)
2. in-order traversal, keep track with the previous value and compare to the current one
3. check whether ALL left nodes are less than or equal to the current node, which must be less than ALL the right nodes
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/bcb725181e5a8f6035f3
【test case】
build binary tree using function developed in 4.3
array = [5 10 25 20 25 30 35]
Expected output: 0 (false)
Approach 1: 1
Approach 2: 0
Approach 3: 0
回复 支持 反对

使用道具 举报

Neal 发表于 2014-7-13 10:30:10 | 显示全部楼层
【解题思路】Inorder transverse the tree, check predecessor is smaller than current node
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist】https://gist.github.com/nealhu/9b8c4f9e306e61c3f0bd
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-7-14 06:08:43 | 显示全部楼层
【解题思路】
recursively traverse the binary tree, compare the node with min and max value
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist】
https://gist.github.com/iwilbert/eb5b9c51613be3224aba
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-16 06:43:55 | 显示全部楼层
【解题思路】
1. min< node.value < max   
2. min< left.value < node.value
3. node.value < right.value < max
【时间复杂度】
O(N)
【空间复杂度】
O(logN)  for recursion calls
【gist link】https://gist.github.com/jyhjuzi/77590c414117f9e4d76d
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-7-16 08:27:08 | 显示全部楼层
【解题思路】min<left<node<right<max
【时间复杂度】o(n)
【空间复杂度】o(lg n)
【gist link】https://gist.github.com/hilda8519/500a5c66a4712965e359
回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-18 06:03:12 | 显示全部楼层
【解题思路】和4.1一样的inorder第归遍历
【时间复杂度】o(n)
【空间复杂度】o(lg n)
【gist link】https://gist.github.com/Noahsark/c1dbb3884d463f9fe0cf
回复 支持 反对

使用道具 举报

tonygxxx1212 发表于 2014-7-19 22:45:54 | 显示全部楼层

【解题思路】
inorder check, use stack
【时间复杂度】
O(N)
【空间复杂度】
O(H)
【gist】https://gist.github.com/xun-gong/321cb6362d95acdb96f9
回复 支持 反对

使用道具 举报

jason51122 发表于 2014-7-29 14:25:36 | 显示全部楼层
【解题思路】Inorder traversal
【时间复杂度】O(N)
【空间复杂度】O(H)
【gist link】https://gist.github.com/jason51122/65eb1683389527029069
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 02:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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