x***i
发帖数: 64 | 1 不知道以前有人贴过不？我是第一次见
把BT sibling 连起来，constant 内存.
1 -->null
2 --> 3 -->null
7 --> 8 -->null |
g*****i
发帖数: 2162 | |
e***s
发帖数: 799 | |
f********e
发帖数: 166 | |
l*****a
发帖数: 14598 | 5 const memory,
how to resolve it?
【在 g*****i 的大作中提到】
: 老题了.
|
g*****i
发帖数: 2162 | 6 在链接第n层的时候,利用已经连接的n-1层,所以维系两个pointer就可以了.
【在 l*****a 的大作中提到】
: const memory,
: how to resolve it?
|
l*****a
发帖数: 14598 | 7 please share your code.thank
or explain how to use the n-1 layer
【在 g*****i 的大作中提到】
: 在链接第n层的时候,利用已经连接的n-1层,所以维系两个pointer就可以了.
|
x***i
发帖数: 64 | 8 我刚写了一遍，没有test
class node {
node *l;
node *r;
node *s;
};
void linksibling(node *root)
{
if (!root) return;
root->s = NULL;
node *c = root, *n, *h;
while (c)
{
// 找下一层的头
while (c && !c->l && !c->r)
c = c->s;
if (!c)
break;
if (c->l)
{
n = c->l;
h = n;
}
if (c->r)
{
if (n)
{
n->s = c->r;
n = c->r;
}
else {
n = c->r;
h = n;
}
}
// 链接下一层
while (c->s)
{
c = c->s;
if (c->l)
{
n->s = c->l;
n = n->s;
}
if (c->r)
{
n->s = c->r;
n = n->s;
}
}
n->s = NULL;
//
c = h;
}
} |
K*******g
发帖数: 26 | 9 跟你的思路一样，不过找第一个结点可以优化以下
struct Node{
int value;
Node *left;
Node *right;
Node *sibling;
};
void connect_sibling(Node *root){
root->sibling = 0;
Node *cur, *dummy;
dummy = new Node;
while(root){
cur = dummy;
while(root){
if(root->left){
cur->sibling = root->left;
cur = root->left;
}
if(root->right){
cur->sibling = root->right;
cur = root->right;
}
root = root->sibling;
}
cur->sibling = 0;
root = dummy->sibling;
}
delete dummy;
}
【在 x***i 的大作中提到】
: 我刚写了一遍，没有test
: class node {
: node *l;
: node *r;
: node *s;
: };
: void linksibling(node *root)
: {
: if (!root) return;
: root->s = NULL;
|
x***i
发帖数: 64 | 10 nice. simple is better, :-).
【在 K*******g 的大作中提到】
: 跟你的思路一样，不过找第一个结点可以优化以下
: struct Node{
: int value;
: Node *left;
: Node *right;
: Node *sibling;
: };
: void connect_sibling(Node *root){
: root->sibling = 0;
: Node *cur, *dummy;
|
|
|
d*******l
发帖数: 338 | 11 厉害！之前这个问题一直没想出特别简洁的办法，这个非常好
【在 K*******g 的大作中提到】
: 跟你的思路一样，不过找第一个结点可以优化以下
: struct Node{
: int value;
: Node *left;
: Node *right;
: Node *sibling;
: };
: void connect_sibling(Node *root){
: root->sibling = 0;
: Node *cur, *dummy;
|
B*******1
发帖数: 2454 | |
v***n
发帖数: 5085 | 13 什么叫constant 内存
示下才搞定。先让不知道答案的xdjm想想吧。回头贴我的做法。
【在 x***i 的大作中提到】
: 不知道以前有人贴过不？我是第一次见
: 把BT sibling 连起来，constant 内存.
: 1 -->null
: 2 --> 3 -->null
: 7 --> 8 -->null
|
c****p
发帖数: 6474 | 14 O(1) space
【在 v***n 的大作中提到】
: 什么叫constant 内存
:
: 示下才搞定。先让不知道答案的xdjm想想吧。回头贴我的做法。
|
g*****i
发帖数: 2162 | 15 1337的assume是full tree
【在 B*******1 的大作中提到】
: 弱问，和1337大牛的这题有什么不同啊？
: http://www.leetcode.com/2010/03/first-on-site-technical-intervi
|
i**********e
发帖数: 1145 | 16 如果不是full tree 也可以解，我那第一个解法稍微改一改就可以解 general case。
第一个解法其实就是相当于 Breadth first traversal而不用额外空间，诀窍在于利用
上一层已经连接好的节点。
【在 g*****i 的大作中提到】
: 1337的assume是full tree
|
B*******1
发帖数: 2454 | 17 还以为大牛不来这里指点大家了。
【在 i**********e 的大作中提到】
: 如果不是full tree 也可以解，我那第一个解法稍微改一改就可以解 general case。
: 第一个解法其实就是相当于 Breadth first traversal而不用额外空间，诀窍在于利用
: 上一层已经连接好的节点。
|
r******n
发帖数: 170 | 18 太巧妙了
不过这种dummy node的trick，估计现场直接写出来，一看就是练过的
【在 K*******g 的大作中提到】
: 跟你的思路一样，不过找第一个结点可以优化以下
: struct Node{
: int value;
: Node *left;
: Node *right;
: Node *sibling;
: };
: void connect_sibling(Node *root){
: root->sibling = 0;
: Node *cur, *dummy;
|
g*****i
发帖数: 2162 | 19 又见大牛,恩你给的解法稍微改下就可以了
【在 i**********e 的大作中提到】
: 如果不是full tree 也可以解，我那第一个解法稍微改一改就可以解 general case。
: 第一个解法其实就是相当于 Breadth first traversal而不用额外空间，诀窍在于利用
: 上一层已经连接好的节点。
|
x***i
发帖数: 64 | 20 如果用recursive for general case, space is O(n) in stack, the height of the
tree.
【在 i**********e 的大作中提到】
: 如果不是full tree 也可以解，我那第一个解法稍微改一改就可以解 general case。
: 第一个解法其实就是相当于 Breadth first traversal而不用额外空间，诀窍在于利用
: 上一层已经连接好的节点。
|
|
|
r******n
发帖数: 170 | 21 假如不考虑recursive用的stack space,似乎还没想出来怎么稍微修改一下就能work?
大牛们，能详细解释下吗？
the
【在 x***i 的大作中提到】
: 如果用recursive for general case, space is O(n) in stack, the height of the
: tree.
|
g***x
发帖数: 494 | 22 1337那第一个方法是tail recursive， 很容易改成loop吧，
void connect_sibling( node * root)
{
if (!root) return;
root->sibling=0;
node * current_level_head=root;
while(current_level_head)
{
node *current_node=current_level_head;
node *next_level_head=0;
while (current_node)
{
if (current_node->left)
{
if (next_level_head==0)
next_level_head=current_node->left;
current_node->left->sibling=0;
if (current_node->right)
current_node->left->sibling=current_node_right;
else if (current_node->sibling)
{
if (current_node->sibling->left)
current_node->left->sibling=current_node->sibling->left;
else if (current_node->sibling->right)
current_node->left->sibling=current_node->sibling->right;
}
}
if (current_node->right)
{
if (next_level_head==0)
next_level_head=current_node->right;
current_node->right->sibling=0;
if (current_node->sibling)
{
if (current_node->sibling->left)
current_node->right->sibling=current_node->sibling->left;
else if (current_node->sibling->right)
current_node->right->sibling=current_node->sibling->
right;
}
}
current_node=current_node->sibling;
}//while (current_node)
current_level_head=next_level_head;
}//while(current_level_head)
} |
a********m
发帖数: 15480 | 23 1337还是careerup有。
示下才搞定。先让不知道答案的xdjm想想吧。回头贴我的做法。
【在 x***i 的大作中提到】
: 不知道以前有人贴过不？我是第一次见
: 把BT sibling 连起来，constant 内存.
: 1 -->null
: 2 --> 3 -->null
: 7 --> 8 -->null
|
d*******u
发帖数: 186 | 24 这个算法太牛了，不知我的理解对不对？
void connect_sibling( Node *root ) {
root->sibling = null;
Node *cur, *dummy;
dummy = new Node;
while( root ) { //dummy->slibling是指向上次下一层的最左节点。
cur = dummy; //这样保证dummy->slibling总指向最左节点
while( root ) { // 找上一层的最右边节点， 假设当前层sibling已连好。
if( root->left ) {
cur->sibling = root->left;
cur = root->left;
}
if(root->right){
cur->sibling = root->right;
cur = root->right;
}
root = root->sibling; //上一层的下一个姐妹，直到最右边。
} //end of while second loop
//此时，下一层已串好。
cur->sibling = null; //最右边下一层填空。
root = dummy->sibling; //上层的右一个节点。
}
delete dummy;
}
【在 K*******g 的大作中提到】
: 跟你的思路一样，不过找第一个结点可以优化以下
: struct Node{
: int value;
: Node *left;
: Node *right;
: Node *sibling;
: };
: void connect_sibling(Node *root){
: root->sibling = 0;
: Node *cur, *dummy;
|
r******n
发帖数: 170 | 25 大家在讨论不是去掉tail recursion，是怎么把1337的第一个方法改成支持not full
binary tree。
你这么写，意思跟KeithDeng的一样吧，代码上却没他的简洁。
在想怎么保留1337的recursion，还能支持所有的binary tree，觉得改动很大，不是大
牛们说的稍微改改
【在 g***x 的大作中提到】
: 1337那第一个方法是tail recursive， 很容易改成loop吧，
: void connect_sibling( node * root)
: {
: if (!root) return;
: root->sibling=0;
: node * current_level_head=root;
:
: while(current_level_head)
: {
: node *current_node=current_level_head;
|
