BST preorder traversal 那道题的最优解法 - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - BST preorder traversal 那道题的最优解法

相关主题
● GOOG phone interview question	● 这个check whether a binary tree is a BST 问题
● [合集] 微软面试的一道题	● 转一些我blog上一些常见的二叉树面试问题和总结
● F家phone interview的一道题	● bloomberg onsite题
● 关于BST traverse的复杂度	● 大概说一下昨天的Google Phone Interview
● Convert Sorted List to BST那道题	● 谷歌电面
● 随便问下，现在面flag是不是都得最优解了？	● 树 inorder下个节点最好办法是啥
● 从tree的post order traversal和pre,能否build这个tree?	● inorder traversal and BST
● BST面试题	● 二叉树如何判断一个节点是不是在另外两个节点的path上。。。。好像是个老题了。。求解？

相关话题的讨论汇总
话题: bst话题: 解法话题: traversal话题: preorder话题: 道题

进入JobHunting版参与讨论

1

(共1页)

x**********z 发帖数: 131	1 题目：给一个int数组，返回一个bool值表示是否可能是一个BST的preorder traversal。 naive解法O(n^2)。另外感觉可以用binary search + segment tree，O(nlogn)。看到有人提到有O(n)的解法，请问有人知道吗？
g******n 发帖数: 10	2 O(n) 时间就可以了，看我的帖子 http://www.mitbbs.com/article/JobHunting/32964269_0.html
b********0 发帖数: 62	3 你这是nlgn的吧... http://www.snippetexample.com/2015/03/verify-preorder-sequence- 上面这个看起来靠谱点【在 g******n 的大作中提到】 : O(n) 时间就可以了，看我的帖子 : http://www.mitbbs.com/article/JobHunting/32964269_0.html
g******n 发帖数: 10	4 刚才看了下，你说得对，我的是 O(n lg n) 的，你的链接里的方法是 O(n) 的，不错，学习了
l******s 发帖数: 3045	5 干净利落，好【在 b********0 的大作中提到】 : 你这是nlgn的吧... : http://www.snippetexample.com/2015/03/verify-preorder-sequence- : 上面这个看起来靠谱点
d******v 发帖数: 801	6 Mark
x**********z 发帖数: 131	7 多谢！【在 b********0 的大作中提到】 : 你这是nlgn的吧... : http://www.snippetexample.com/2015/03/verify-preorder-sequence- : 上面这个看起来靠谱点

1

(共1页)

进入JobHunting版参与讨论

相关主题
● 二叉树如何判断一个节点是不是在另外两个节点的path上。。。。好像是个老题了。。求解？	● Convert Sorted List to BST那道题
● Restore binary tree from preorder and inorder sequences	● 随便问下，现在面flag是不是都得最优解了？
● BFS traverse O(1) space?	● 从tree的post order traversal和pre,能否build这个tree?
● 说说面了几个老印的体会	● BST面试题
● GOOG phone interview question	● 这个check whether a binary tree is a BST 问题
● [合集] 微软面试的一道题	● 转一些我blog上一些常见的二叉树面试问题和总结
● F家phone interview的一道题	● bloomberg onsite题
● 关于BST traverse的复杂度	● 大概说一下昨天的Google Phone Interview

相关话题的讨论汇总
话题: bst话题: 解法话题: traversal话题: preorder话题: 道题

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)