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 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 和BST没有关系，只要是tree traversal都应该是O(N), where N is the size of the
tree. |
|
M7
发帖数: 219 | 4 traversal和search有什么关系？为什么要search? |
|
t**r
发帖数: 512 | 5 we can do this as in order traverse without recursion |
|
j*****u
发帖数: 1133 | 6 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 严格地说 degree bounded 好像是既有upper bound, 又有lower bound （leaf nodes
除外）
举个特例，balanced BST应该符合这个要求吧？但想不出怎么做BFS traverse with O(
1) space |
|
t*****s
发帖数: 416 | 9 balanced BST 的话traverse几乎不需要空间吧？
nodes
O( |
|
c******t
发帖数: 391 | 10 今天面试码工职位,被问到了一道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 原帖里说了“返回从起始点出发的traversal是否能cover矩阵里的每一个点。” |
|
g****y
发帖数: 240 | 12 他的意思是，traversal可能已经cover了所有的点，但是最后一个点并不指向起始点。
[(0,1)(1,0)]
[(1,1)(1,1)]
起始点是（0，0） |
|
R********y
发帖数: 88 | 13 这种情况下根本就不存在“返回从起始点出发的traversal”。 |
|
g****y
发帖数: 240 | 14 “返回从起始点出发的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的算法一样
，没有什么特殊算法？ |
|
|
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 这个binary tree iterative traversal 的codes 貌似不对，再仔细看看 |
|
n****e
发帖数: 678 | 26 你太客气了，不用抱歉哈 :)
这个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 得留个心眼,很多TR都彼此矛盾的. 譬如Cooper的书上说traverse起始处的高度是13,
800,我们俩在那附近转悠了近半个小时,放眼望去全是4+的东东,无处下嘴.后来只好再
往下走了不少才找到的,看我的GPS,已经13,600了. |
|
|
E*******e
发帖数: 1371 | 36 这种比较短的low class 5 一般不需要保护。Bells traverse确实有少数人是用了绳子
的，但是据说会大大的减慢进程。
其实这几处墙都比较好爬，手抓脚踩的地方非常多，只要有信心绝大多数人都是可以爬
过去的。 |
|
E*******e
发帖数: 1371 | 37 你要是有兴趣的话轻松搞定肯定不成问题的。Roach的书上说这个traverse是class4也
并非没有道理 |
|
|
i***g
发帖数: 262 | 39 想买chevy traverse。。不知道今年有木有团购。。 |
|
s**********e
发帖数: 46 | 40 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 想这个周末去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, :) |
|
