由买买提看人间百态

topics

全部话题 - 话题: traversal
首页 上页 1 2 3 4 5 6 7 8 9 10 (共10页)
x***y
发帖数: 633
1
Hi, it's right. Actually, this approach is not the reverse of level by level
, but it's the reverse of pre-order traversal of the mirror of the original
tree. The first stack is only used for the pre-order of the mirror, and the
second is to reverse. It will be easier to understand if we say it's just a pre-order....
m*****e
发帖数: 47
2
来自主题: JobHunting版 - inorder traversal and BST
If an inorder traversal on a binary tree gets the elements in sorted order,
does it necessarily prove it is a binary search tree?
M7
发帖数: 219
3
来自主题: JobHunting版 - 关于BST traverse的复杂度
和BST没有关系,只要是tree traversal都应该是O(N), where N is the size of the
tree.
M7
发帖数: 219
4
来自主题: JobHunting版 - 关于BST traverse的复杂度
traversal和search有什么关系?为什么要search?
t**r
发帖数: 512
5
来自主题: JobHunting版 - 关于BST traverse的复杂度
we can do this as in order traverse without recursion
j*****u
发帖数: 1133
6
来自主题: JobHunting版 - 关于BST traverse的复杂度
I think you answered your question yourself :)
in-order non-recursive traversal is O(n) since you push/pop every node into
the queue exactly once
v*******7
发帖数: 187
7

tree,
child
I am wondering whether such solution exists. Traversal of a tree without
recursion
can be done by either Queue-based or Stack-based. But if the space required
is no
more than constant, it means that the space allocated to Queue or Stack is
constant.
But I have no idea on how to deal with it by using Q/S with constant space
forever.
l*****g
发帖数: 685
8
来自主题: JobHunting版 - BFS traverse O(1) space?
严格地说 degree bounded 好像是既有upper bound, 又有lower bound (leaf nodes
除外)
举个特例,balanced BST应该符合这个要求吧?但想不出怎么做BFS traverse with O(
1) space
t*****s
发帖数: 416
9
来自主题: JobHunting版 - BFS traverse O(1) space?
balanced BST 的话traverse几乎不需要空间吧?

nodes
O(
c******t
发帖数: 391
10
来自主题: JobHunting版 - 一道关于matrix traversal的面试题
今天面试码工职位,被问到了一道coding题,说有一个m x n的二维矩阵Item[][],每一
个元素都是一个Item类的object, 其中Item类定义如下:
public class Item{
public int x; //
public int y;
}
x和y分别是矩阵里的另一个元素的横纵坐标。实现一个函数,给定一个起始点的横纵坐
标startX 和startY,返回从起始点出发的traversal是否能cover矩阵里的每一个点。
我的想法是用一个hashSet,每初始化一个Item,都放入这个set, 直到遇到重复元素
或null为止,然后计算hashSet的size是否等于matrix的size。我写的基本算法:
boolean getCoverage(Item[][] items, int startX, int startY){
Item item = items[startX][starty];
HashSet set = new HashSet();
set.add(item);
while(item... 阅读全帖
R********y
发帖数: 88
11
来自主题: JobHunting版 - 一道关于matrix traversal的面试题
原帖里说了“返回从起始点出发的traversal是否能cover矩阵里的每一个点。”
g****y
发帖数: 240
12
来自主题: JobHunting版 - 一道关于matrix traversal的面试题
他的意思是,traversal可能已经cover了所有的点,但是最后一个点并不指向起始点。
[(0,1)(1,0)]
[(1,1)(1,1)]
起始点是(0,0)
R********y
发帖数: 88
13
来自主题: JobHunting版 - 一道关于matrix traversal的面试题
这种情况下根本就不存在“返回从起始点出发的traversal”。
g****y
发帖数: 240
14
来自主题: JobHunting版 - 一道关于matrix traversal的面试题
“返回从起始点出发的traversal”是什么意思。。。。
c****7
发帖数: 13
15
各位高手,我想用 Pre-Order Traversal 来实现 maxDepth()。 我用了个hashmap来
保存各个节点的高度.不知道有没有跟优化的解法, 谢谢了!
Here is my code:
public static int maxDepth_preOrderTraversal(TreeNode root){
int maxHight =1;
HashMap nodeHashMap = new HashMap();
if (root==null) return 0;
Stack nodeStack = new Stack();
TreeNode curNode;
nodeStack.push(root);
nodeHashMap.put(root, 1);
while(!nodeStack.isEmpty()){
curNode = nodeStack.pop();
if(curNode.right!=null){
nodeStack.pu... 阅读全帖
c********t
发帖数: 5706
16
Given a binary tree, return the bottom-up level order traversal of its nodes
' values. (ie, from left to right, level by level from leaf to root).
我用层打印存入ArrayList,然后翻转ArrayList解的。大侠女侠们用没有更好的方法?
l****i
发帖数: 2772
17
看到前面帖子里的面经,请教,Binary Tree Level Traversal有recursive的算法么?
s******n
发帖数: 20
18
什么叫没什么意思?你的意思是说和Binary Tree Level Order Traversal的算法一样
,没有什么特殊算法?
w******j
发帖数: 185
19
这个题,如果不是最好return arraylist的话,
http://www.geeksforgeeks.org/reverse-level-order-traversal/
但是最后它还是return arraylist了,这样的话,这道题就没什么意思了....也看不出
来做法不一样了...
u*****o
发帖数: 1224
20
弱问LZ,面试官说一定要用iterator了是吗? in order traversal用threaded trees
不是更好吗,不用stack. 还是他就说要考察iterator的使用?
s*******n
发帖数: 305
21
之前用array+list实现hashtable的时候写过一个相应的iterator, 这方面实在是基础
很差..., 最后是在hashtable 定义了一个方法, 把所有数据都放到一个
arraylist里面(类似于楼主的traversal()), 然后再由Iterator get 到, 怎么都感
觉象是个伪Iterator...
要是面试碰到楼主这个题, 肯定跪了, 楼主的解法很精妙, mark.
祝楼主好运, 拿到onsite
u*****o
发帖数: 1224
22
且听本姑娘一一道来
1. pre-order recursive solution
2. pre-order iterative solution using stack
3. pre-order iteration using an iterator with stack
4. in-order recursive solution
5. in-order iterative solution using stack
6. in-order iteration using an iterator with stack
7. in-order iterative solution without stack, without parent pointer (
threaded tree)
8. in-order iterative solution without stack, with parent pointer
9. post-order recursive
10. post-order iterative using one stack
11. post-order itera... 阅读全帖
r*********n
发帖数: 4553
23
刚才没仔细看,还以为你漏掉了Morris in-order traversal
貌似还有类似的pre-order/ post-order
l****k
发帖数: 33
24
morris traverse还是有用的。至少onsite的的时候别人问你follow up的问题可能会答
到。我没有问到过,不过一个哥们面MS的时候问到了。
n****e
发帖数: 678
25
来自主题: JobHunting版 - 问tree的iterative traversal
这个binary tree iterative traversal 的codes 貌似不对,再仔细看看
n****e
发帖数: 678
26
来自主题: JobHunting版 - 问tree的iterative traversal
你太客气了,不用抱歉哈 :)
这个codes还是不对,你是想写post-order iterative traversal吧
你试着run这个test:
1
2 3
4 5 6 7
这个condition: if(!node->right && !node->left) 对node 2, node 3 不work
a***e
发帖数: 413
27
下面这两个1.2.写法都是O(N^2)吧?为啥2说是O(N)呢?另外,看到lc上一个
discussion的iterative的解法3.https://oj.leetcode.com/discuss/2297/the-
iterative-solution-is-easier-than-you-think
时间复杂度是O(N)吧?
我看了helper的function signature能写出1,对2中用到的好多STL要搜索才能写出来
,不熟。
Binary tree和recursion现在是我最弱处,多谢!
1.
class Solution {
public:
TreeNode *buildTree(vector &preorder, vector &inorder) {
if (preorder.size()==0) return NULL;
else if (preorder.size()==1)
{
TreeNode *t = new TreeNode(preorder[0])... 阅读全帖
d********o
发帖数: 12
28
这种方法确实是O(h)
如果用Morris Traversal,空间复杂度O(1)
S*******C
发帖数: 822
29
连Morris Traversal都会写的人至少刷了500道题吧
d*****h
发帖数: 8
30
Dear Colleagues,
I want to ask an algorithm question:
Given a vector of int, which is the output of level first traversal of a
binary search tree, build the original BST. O(n) time complexity is required.
Thanks,
dbtouch
x**********z
发帖数: 131
31
题目:给一个int数组,返回一个bool值表示是否可能是一个BST的preorder traversal。
naive解法O(n^2)。
另外感觉可以用binary search + segment tree,O(nlogn)。
看到有人提到有O(n)的解法,请问有人知道吗?
D*******o
发帖数: 3229
32
我家落地窗原配的traverse curtain rod里面的一个小的滑轮坏了。原来房主留下的东
西看上去挺高档的,如果因为这么个小零件就换新的有点浪费,所以打算自己或请人修
一修。请高人指点,这个零件叫什么,以及什么地方可以买到。我昨天到Home Depot转
了一圈,没有。
B*N
发帖数: 164
33
6/22: Pre-Presidential Traverse Warm-Up Hike #1: Mt. Madison and Mt. Adams
Mt. Adams, 5799 ft, Mt. Madison,5366 ft. the 2nd and the 5th highest
mountains in the
White Mountains area.
Total Distance: 10.1 miles
Total Elevation gain: 5050 ft
Car pool: $20/person
Bring lunch and water
We leave at 7:00AM
You need have a lot of hiking experience and all necessary hiking gears for
this hike.
Let me know if you want to join us: 6173722058
Boston Professional Networking (BPN), a non-profit organization,... 阅读全帖
s*****n
发帖数: 617
34
来自主题: Colorado版 - [TR] Crestone Traverse and Humboldt
得留个心眼,很多TR都彼此矛盾的. 譬如Cooper的书上说traverse起始处的高度是13,
800,我们俩在那附近转悠了近半个小时,放眼望去全是4+的东东,无处下嘴.后来只好再
往下走了不少才找到的,看我的GPS,已经13,600了.
E*******e
发帖数: 1371
35
【 以下文字转载自 Outdoors 讨论区 】
发信人: Extensive (███████████████████), 信区: Outdoors
标 题: 【TR】Maroon Bells Traverse (多图)
发信站: BBS 未名空间站 (Fri Oct 4 01:45:53 2013, 美东)
图放在帖子里看太小了很不爽。弄了个链接,图可以显示得比较大:
http://sites.google.com/site/zksposts/home/maroon-bells-travers
一点thumbnails
E*******e
发帖数: 1371
36
这种比较短的low class 5 一般不需要保护。Bells traverse确实有少数人是用了绳子
的,但是据说会大大的减慢进程。
其实这几处墙都比较好爬,手抓脚踩的地方非常多,只要有信心绝大多数人都是可以爬
过去的。
E*******e
发帖数: 1371
37
你要是有兴趣的话轻松搞定肯定不成问题的。Roach的书上说这个traverse是class4也
并非没有道理
E*******e
发帖数: 1371
i***g
发帖数: 262
39
来自主题: Georgia版 - 想买chevy traverse,有团购么?
想买chevy traverse。。不知道今年有木有团购。。
s**********e
发帖数: 46
40
来自主题: Michigan版 - List of things to do in Traverse City
I used to live in Traverse City so I think I know abit about that place. :-)
Lots people are visiting up north for the coming weekend so here is a list
of things to do.
First of all, July 5-12 is annual cheery festival. Please check out there
website to fit interesting activities into your schedule.
http://www.cherryfestival.org/default.php#1a
Basically, like any places in Northern Michigan, you are there to see beach,
small downtown, food, view and wine.
http://www.visittraversecity.com/
Websit
m***m
发帖数: 72
41
来自主题: Michigan版 - traverse city的hotel
想这个周末去traverse city和sleeping bear玩,但查了一下hotel和motel,最便宜的
super8都要130/night。
请问哪里可以查到便宜点的私人出租的房子,或者其他更好选择呢
p******y
发帖数: 496
42
Traverse city,Porcupine Mountain,Copper Harbor这些地方,哪里景色更壮观些?
有几个朋友准备从加州德州麻省飞过来,待一个周末或者三天,Novi哥建议去什么地方
看?
i********g
发帖数: 45
43
几个星期前,从Machinaw City开到Traverse City,一路起伏不平,55的限速开到80,
很爽。如果有红叶,算了不想了。
不去UP用不了三天。
N**i
发帖数: 3857
44
10/2 周末可以去Iron Mountain,Picture Rock一线
10/9周末可以去 Traverse City, Petoskey, Au Sable River Drive一线。
10/15 周末NY五指湖地区也不错。
10/22周末,西宾,西伏地区应该都红了。
r*****e
发帖数: 4598
45
traverse那边是不是1月到3月很难开车进去啊 大雪会影响路况么?
d*****o
发帖数: 2868
46
the driving condition in traverse city during the winter time isn't that bad
. Even if there is a big snow storm, the roads get cleaned on a regular
basis. Just be really careful if you are planning to drive from TC to
sleeping bear dunes during the winter time, the roads can be extremely
treacherous.
h******e
发帖数: 101
47
国庆节想去traverse city转转,但是只知道那附近有个sleeping bear dune,好像还
有一个festival,各位谁知道那附近有什么好玩的,麻烦您帮着推荐推荐,另外国庆节
其他地方还有什么有意思的活动嘛?比如德国镇等地方,
非常感激,
x**********e
发帖数: 924
48
准备明天早上从Ann Arbor出发 去Traverse City,
计划在那里住一晚,然后第二天下午返回
求推荐值得去的地方, Sleep bear可以去那个岛上么? 有什么注意事项
多谢
r****r
发帖数: 701
49
sleep bear dune的national park大概1个小时,除非你要爬沙丘
然后沙滩不错。
traverse city的沙滩一般,人挺多还收费,那个尖尖的岛上有很多酒庄
d*****o
发帖数: 2868
50
TC的beach不收费吧?就是夏天的时候去的话,人稍微多一些。
traverse city就是一个笔吃,没啥好看的。sleeping bear dunes需要走trail, 不然
没意思。不过sleeping bear dunes的东北部有个叫做leland的小town, 从那里可以坐
船去一个叫做manitou的小岛。那个岛上如果hike到山顶,7mi round trip, 山顶的风
景还是不错的。lz要是感兴趣的话可以google 戴硕北密游记,我以前发过这2个地方的
游记。
hope what i wrote helps, and no need for baozi, :)
首页 上页 1 2 3 4 5 6 7 8 9 10 (共10页)