c*****y
发帖数: 90 | 1 Given a binary tree
struct node{
struct node* leftChild;
struct node* rightChild;
struct node* nextRight;
}
The nextRight points to the right node to the current node in the same
level. Ask you populate the nextRight pointers in each node.
大家怎么做这道题. |
m*****f
发帖数: 1243 | 2 记得以前有个分level打印二叉树的题目么， 这两道题本质上是一样的 |
a*******g
发帖数: 12 | 3 BFS
【在 c*****y 的大作中提到】
: Given a binary tree
: struct node{
: struct node* leftChild;
: struct node* rightChild;
: struct node* nextRight;
: }
: The nextRight points to the right node to the current node in the same
: level. Ask you populate the nextRight pointers in each node.
: 大家怎么做这道题.
|
c*****y
发帖数: 90 | 4 对，就是每个node从queue里面dequeue出来后它的nextRight指向queue的peek。
我现在在想，能否有recursion的方法？想了下想不出来。
【在 m*****f 的大作中提到】
: 记得以前有个分level打印二叉树的题目么， 这两道题本质上是一样的
|
b****j
发帖数: 78 | 5 可以使用任何方式遍历一遍这棵树，iterative or recurise
在遍历过程中，对每一个节点x
if (x->leftChild and x->rightChild) {
x->leftChild->nextRight = x->rightChild;
x->rightChild->nextRight = 0;
}
【在 c*****y 的大作中提到】
: Given a binary tree
: struct node{
: struct node* leftChild;
: struct node* rightChild;
: struct node* nextRight;
: }
: The nextRight points to the right node to the current node in the same
: level. Ask you populate the nextRight pointers in each node.
: 大家怎么做这道题.
|
c*****y
发帖数: 90 | 6 这个主要看如何理解这道题，如果认为nextRight是指向同一parent点下的右边点，你
可以这么做。
如果是指同一level的右边点，那么只能用bfs了。
【在 b****j 的大作中提到】
: 可以使用任何方式遍历一遍这棵树，iterative or recurise
: 在遍历过程中，对每一个节点x
: if (x->leftChild and x->rightChild) {
: x->leftChild->nextRight = x->rightChild;
: x->rightChild->nextRight = 0;
: }
|
b****j
发帖数: 78 | 7 I see, then BFS!
【在 c*****y 的大作中提到】
: 这个主要看如何理解这道题，如果认为nextRight是指向同一parent点下的右边点，你
: 可以这么做。
: 如果是指同一level的右边点，那么只能用bfs了。
|
b***e
发帖数: 1419 | 8 这题水深了. 你的研究客户心理. 明显不是BFS. 对于平衡树来讲, BFS的space
complexity
是O(n)的. DFS一般是O(log(n))的. 一般树都比较平衡, 否则比较傻逼. 这个分三步:
第一步, 如果有parent pointer, 就就这么做:
void linkNext(node * current) {
if (!current) {
return;
}
if (current->nextRight) {
return;
}
node * parent = current->parent;
if (!parent) {
current->nextRight = NULL;
} else if (current == parent->leftChild && parent->rightChild) {
current->nextRight = parent->rightChild;
} else {
node
【在 c*****y 的大作中提到】
: 对，就是每个node从queue里面dequeue出来后它的nextRight指向queue的peek。
: 我现在在想，能否有recursion的方法？想了下想不出来。
|
v*****t
发帖数: 127 | 9 其实从上往下，遍历一层链的过程中链接下一层链，这样就不需要parent指针了。因为
在生成下一层链的时候，当前的这个节点就是下一层的parent。
步:
【在 b***e 的大作中提到】
: 这题水深了. 你的研究客户心理. 明显不是BFS. 对于平衡树来讲, BFS的space
: complexity
: 是O(n)的. DFS一般是O(log(n))的. 一般树都比较平衡, 否则比较傻逼. 这个分三步:
: 第一步, 如果有parent pointer, 就就这么做:
: void linkNext(node * current) {
: if (!current) {
: return;
: }
: if (current->nextRight) {
: return;
|
b***e
发帖数: 1419 | 10 没说到点上。
其实这题的意思是用nextRight来代替queue, 不要新空间。 就像用parent来代替栈一
样。
【在 v*****t 的大作中提到】
: 其实从上往下，遍历一层链的过程中链接下一层链，这样就不需要parent指针了。因为
: 在生成下一层链的时候，当前的这个节点就是下一层的parent。
:
: 步:
|
|
|
g*******y
发帖数: 1930 | 11 在一层上遍历完了一条链(由nextRight串起来的链)生成下一层新的一条链，然后再遍历新的链继续生成新的链。。。这不就相当于是用nextRight代替queue嘛
当然，没有你表述的那么清晰，呵呵
有了queue就不需要stack了，所以不需要用到parent了嘛
【在 b***e 的大作中提到】
: 没说到点上。
: 其实这题的意思是用nextRight来代替queue, 不要新空间。 就像用parent来代替栈一
: 样。
|
m*****f
发帖数: 1243 | 12 一针见血啊, 明白了
【在 b***e 的大作中提到】
: 没说到点上。
: 其实这题的意思是用nextRight来代替queue, 不要新空间。 就像用parent来代替栈一
: 样。
|
b***e
发帖数: 1419 | 13 其实这个题我真的遇到过。说起来都容易，现场写code不好写。尤其是白板上。
【在 m*****f 的大作中提到】
: 一针见血啊, 明白了
|
k***e
发帖数: 556 | 14 大牛怎么最近开始用中文了
有没有机会refer我一下 ：）
【在 b***e 的大作中提到】
: 其实这个题我真的遇到过。说起来都容易，现场写code不好写。尤其是白板上。
|
b****j
发帖数: 78 | 15 好主意, 原题没有说清楚需要空间O(1)，时间O(n)，把这个算法实现了一下，没有运行
过：
void check(Node *p, Node* &last, Node* &first) {
if (p) {
if (last)
last->nextRight = p;
else
first = p;
last = p;
}
}
void link_next_right(Node *root) {
if (root)
root->nextRight = NULL;
for (Node *first=root, *next_first=NULL;
first;
first=next_first, next_first=NULL) {
Node *last = NULL;
for (Node *p=first; p; p=p->nextRight) {
check(p->leftChild, last, next_first);
check(p->ri
【在 g*******y 的大作中提到】
: 在一层上遍历完了一条链(由nextRight串起来的链)生成下一层新的一条链，然后再遍历新的链继续生成新的链。。。这不就相当于是用nextRight代替queue嘛
: 当然，没有你表述的那么清晰，呵呵
: 有了queue就不需要stack了，所以不需要用到parent了嘛
|
h*********e
发帖数: 56 | 16 should the rightmost one in a level point to NULL, or to the leftmost one in
the next level? |
b****j
发帖数: 78 | 17 NULL, if it were the leftmost one in the next level, the code could be furth
er simplified.
in
【在 h*********e 的大作中提到】
: should the rightmost one in a level point to NULL, or to the leftmost one in
: the next level?
|
