由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - G题,把binary tree里面的sibling节点连接起来
相关主题
一道面试题生成树
问道G家的面试题。做了一下merge BST
MS on-site 面经&求分析(口头offer)攒人品,Twitter 电面题目
binary tree的in-order iterator怎么写?贡献一道G家的onsite题和简单面经(已悲剧)
这个check whether a binary tree is a BST 问题今天面的太惨了....
A家,link all node in the same lev很可能被这题搞挂了,sort linked list
一个老题binary tree找 lowest common ancestor 的code (请教请问如何sort一个linked list?
讨论Amazon的一道题:根节点到叶节点之间最小和,并打印路径Populating Next Right Pointers in Each Node II
相关话题的讨论汇总
话题: null话题: node话题: cur话题: root话题: nexthead
进入JobHunting版参与讨论
1 (共1页)
c********t
发帖数: 5706
1
我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
存进去,第二遍再把每个list里的nodes连起来
记得这道题前一阵讨论过,谁能帮我找到。
g**e
发帖数: 6127
2
跟按层打印node没分别吧

【在 c********t 的大作中提到】
: 我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
: 存进去,第二遍再把每个list里的nodes连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

c********t
发帖数: 5706
3
还是有分别的,层打印很多节点要走多遍

【在 g**e 的大作中提到】
: 跟按层打印node没分别吧
j*****o
发帖数: 394
4
我amazon onsite考过这题
可以O(n)时间 O(1)空间的。
用2个指针,一个指着 i层,一个指着 i+1层这样子。(当然另外还要指针)
就是 i 层指针从左到右跑的时候把 i+1 层的全连好了。
不知说清楚没有><

【在 c********t 的大作中提到】
: 我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
: 存进去,第二遍再把每个list里的nodes连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

b***m
发帖数: 5987
5
说得很清楚了,基本就是这么做的。遍历某一层时,把下一层保存到一个queue或者
vector中。

【在 j*****o 的大作中提到】
: 我amazon onsite考过这题
: 可以O(n)时间 O(1)空间的。
: 用2个指针,一个指着 i层,一个指着 i+1层这样子。(当然另外还要指针)
: 就是 i 层指针从左到右跑的时候把 i+1 层的全连好了。
: 不知说清楚没有><

w****x
发帖数: 2483
6
/*
add sibling pointer to the right sibling of each node in a tree, O(n) time,
O(1) space.
5 minutes thinking, 10 minutes coding, a hint he gave me: recursion
*/
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE* pSibling;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL), pSibling(NULL) {}
};
void LinkRightFromParent(NODE* pNode, NODE* pParent)
{
if (pNode == NULL) return;
//Under this situation, the current node will connect to the child of
current parent
if (pParent != NULL && pParent->pLft == pNode && pParent->pRgt != NULL)
pNode->pSibling = pParent->pRgt;
else //pitfall: when starting from parent chain search, should start at
//the next node to the parent. E.g, if a parent got a left child
and
//right child, and the current node is right child, then the right
child
//will connect to the left child, then dead loop!!!!
{
NODE* pIter = pParent == NULL ? NULL : pParent->pSibling;
//logic below is to find the next right node by parent chain
NODE* pRgtCon = NULL;
while (pIter != NULL && pRgtCon == NULL)
{
if (pIter->pLft != NULL)
pRgtCon = pIter->pLft;
else if (pIter->pRgt != NULL)
pRgtCon = pIter->pRgt;
pIter = pIter->pSibling;
}
pNode->pSibling = pRgtCon;
}
LinkRightFromParent(pNode->pRgt, pNode);
LinkRightFromParent(pNode->pLft, pNode);
}
c********t
发帖数: 5706
7
明白了,我是你这个思路,但是中间存的太多,看来很多余。我试试你的,多谢。

【在 j*****o 的大作中提到】
: 我amazon onsite考过这题
: 可以O(n)时间 O(1)空间的。
: 用2个指针,一个指着 i层,一个指着 i+1层这样子。(当然另外还要指针)
: 就是 i 层指针从左到右跑的时候把 i+1 层的全连好了。
: 不知说清楚没有><

p*****2
发帖数: 21240
8

,
这题感觉BFS逻辑简单很多吧。你面试要求DFS做?

【在 w****x 的大作中提到】
: /*
: add sibling pointer to the right sibling of each node in a tree, O(n) time,
: O(1) space.
: 5 minutes thinking, 10 minutes coding, a hint he gave me: recursion
: */
: struct NODE
: {
: int nVal;
: NODE* pLft;
: NODE* pRgt;

p*****2
发帖数: 21240
9

他说的是O(1) space, 不用queue。

【在 b***m 的大作中提到】
: 说得很清楚了,基本就是这么做的。遍历某一层时,把下一层保存到一个queue或者
: vector中。

p*****2
发帖数: 21240
10

为什么?

【在 c********t 的大作中提到】
: 还是有分别的,层打印很多节点要走多遍
相关主题
A家,link all node in the same lev生成树
一个老题binary tree找 lowest common ancestor 的code (请教做了一下merge BST
讨论Amazon的一道题:根节点到叶节点之间最小和,并打印路径攒人品,Twitter 电面题目
进入JobHunting版参与讨论
p*****2
发帖数: 21240
11
我写了一个,有点繁琐,还没测试。
void connectSibling(Node root)
{
assert(root!=null);

Node[] layer = new Node[2];
layer[0]=root;
int i=0;

while(layer[i%2]!=null)
{
Node prev=null;
Node curr=layer[i%2];

while(curr!=null)
{
if(curr.left!=null)
{
if(prev==null)
{
prev=curr.left;
layer[(i+1)%2]=prev;
}
else
{
prev.sibling=curr.left;
prev=prev.sibling;
}
}

if(curr.right!=null)
{
if(prev==null)
{
prev=curr.right;
layer[(i+1)%2]=prev;
}
else
{
prev.sibling=curr.right;
prev=prev.sibling;
}
}

curr=curr.sibling;
}
layer[i%2]=null;
i++;
}
}
w****x
发帖数: 2483
12

这题印象很深刻啊, 先上BFS再上DFS

【在 p*****2 的大作中提到】
: 我写了一个,有点繁琐,还没测试。
: void connectSibling(Node root)
: {
: assert(root!=null);
:
: Node[] layer = new Node[2];
: layer[0]=root;
: int i=0;
:
: while(layer[i%2]!=null)

b***m
发帖数: 5987
13

哦,对,我没仔细看。

【在 p*****2 的大作中提到】
: 我写了一个,有点繁琐,还没测试。
: void connectSibling(Node root)
: {
: assert(root!=null);
:
: Node[] layer = new Node[2];
: layer[0]=root;
: int i=0;
:
: while(layer[i%2]!=null)

p*****2
发帖数: 21240
14

这样呀。 DFS一定先搞右边再搞左边吧。一会儿写一个。

【在 w****x 的大作中提到】
:
: 这题印象很深刻啊, 先上BFS再上DFS

l*****a
发帖数: 14598
15
太繁琐
直接让回家

【在 p*****2 的大作中提到】
: 我写了一个,有点繁琐,还没测试。
: void connectSibling(Node root)
: {
: assert(root!=null);
:
: Node[] layer = new Node[2];
: layer[0]=root;
: int i=0;
:
: while(layer[i%2]!=null)

p*****2
发帖数: 21240
16
写了一个DFS的
Node findNext(Node node)
{
if(node==null)
return null;

while(node!=null)
{
if(node.left!=null)
return node.left;
if(node.right!=null)
return node.right;

node=node.sibling;
}

return null;
}

void dfs(Node node, Node parent)
{
if(node==null)
return;

if(node==parent.left && parent.right!=null)
{
node.sibling=parent.right;
}
else
{
node.sibling=findNext(parent.sibling);
}

dfs(node.right,node);
dfs(node.left,node);
}

void connectSibling(Node root)
{
assert(root!=null);
dfs(root.right,root);
dfs(root.left,root);
}
l*****a
发帖数: 14598
17
find next复杂度多少?
每个node再求一遍next
感觉复杂度太高了

【在 p*****2 的大作中提到】
: 写了一个DFS的
: Node findNext(Node node)
: {
: if(node==null)
: return null;
:
: while(node!=null)
: {
: if(node.left!=null)
: return node.left;

l*****a
发帖数: 14598
18
一个dummy node,指的都是现有node,并不消费额外空间

【在 c********t 的大作中提到】
: 明白了,我是你这个思路,但是中间存的太多,看来很多余。我试试你的,多谢。
p*****2
发帖数: 21240
19

findnext一般很快就退出了吧?如果都没有children的话,也就被多扫一边。

【在 l*****a 的大作中提到】
: find next复杂度多少?
: 每个node再求一遍next
: 感觉复杂度太高了

l*****a
发帖数: 14598
20
复杂度不能用很快描述吧?
肯定是1 or n 相关啊

【在 p*****2 的大作中提到】
:
: findnext一般很快就退出了吧?如果都没有children的话,也就被多扫一边。

相关主题
贡献一道G家的onsite题和简单面经(已悲剧)请问如何sort一个linked list?
今天面的太惨了....Populating Next Right Pointers in Each Node II
很可能被这题搞挂了,sort linked list发几个面试题
进入JobHunting版参与讨论
p*****2
发帖数: 21240
21

你觉得不是O(n)吗?

【在 l*****a 的大作中提到】
: 复杂度不能用很快描述吧?
: 肯定是1 or n 相关啊

l*****a
发帖数: 14598
22
不认为。
元芳,你怎么看? ==> to wwwyhx

【在 p*****2 的大作中提到】
:
: 你觉得不是O(n)吗?

c********t
发帖数: 5706
23
你如果说的是 breadth first travel, 是用queue走一遍,但没法做到分层
如果是层打印,我只会写以下代码,不但需要多次access nodes,还要先求高度。你有
什么办法一次遍历层打印吗?多谢。
public void printLevelOrder() {
for (int i = 1; i <= this.maxHeight(); i++) {
printLevel(this, i);
System.out.println();
}
}
public void printLevel(Node node, int level) {
if (node == null)
return;
if (level == 1)
System.out.print(node.value + " ");
else {
printLevel(node.left, level - 1);
printLevel(node.right, level - 1);
}
}


【在 p*****2 的大作中提到】
:
: 你觉得不是O(n)吗?

l*****a
发帖数: 14598
24
user Vector/ArrayList之类的咚咚
每次print First item ,remove from head and insert its children into the tail
of the structure.

【在 c********t 的大作中提到】
: 你如果说的是 breadth first travel, 是用queue走一遍,但没法做到分层
: 如果是层打印,我只会写以下代码,不但需要多次access nodes,还要先求高度。你有
: 什么办法一次遍历层打印吗?多谢。
: public void printLevelOrder() {
: for (int i = 1; i <= this.maxHeight(); i++) {
: printLevel(this, i);
: System.out.println();
: }
: }
: public void printLevel(Node node, int level) {

c********t
发帖数: 5706
25
你说用queue? 那就是breadth frst travel吧。。
我可能没说清楚,我觉得breadth first travel不能做到分层,只能做到遍历啊
比如我想要的打印结果如下,是分层的
1
2 3
4 5 6
你说的方法能做到吗?

tail

【在 l*****a 的大作中提到】
: user Vector/ArrayList之类的咚咚
: 每次print First item ,remove from head and insert its children into the tail
: of the structure.

x*****n
发帖数: 195
26
不错!i层已经被link到一起了,挨个扫描和处理i+1层的nodes就行。

【在 b***m 的大作中提到】
: 说得很清楚了,基本就是这么做的。遍历某一层时,把下一层保存到一个queue或者
: vector中。

l*****a
发帖数: 14598
27
我认为能,你怎么看?
你每次处理完一层,记录下tail就可以了,每次处理到这里,就知道一层结束了

【在 c********t 的大作中提到】
: 你说用queue? 那就是breadth frst travel吧。。
: 我可能没说清楚,我觉得breadth first travel不能做到分层,只能做到遍历啊
: 比如我想要的打印结果如下,是分层的
: 1
: 2 3
: 4 5 6
: 你说的方法能做到吗?
:
: tail

K*********n
发帖数: 2852
28
不要用recursion,用queue
Node cur = root;
q.enqueue(cur);
while(!q.isEmpty()){
cur = q.dequeue();
System.out.println(cur.data);
if (cur.left != null)
q.enqueue(cur.left);
if (crur.right != null)
q.enqueue(cur.right);
}

【在 c********t 的大作中提到】
: 你如果说的是 breadth first travel, 是用queue走一遍,但没法做到分层
: 如果是层打印,我只会写以下代码,不但需要多次access nodes,还要先求高度。你有
: 什么办法一次遍历层打印吗?多谢。
: public void printLevelOrder() {
: for (int i = 1; i <= this.maxHeight(); i++) {
: printLevel(this, i);
: System.out.println();
: }
: }
: public void printLevel(Node node, int level) {

K*********n
发帖数: 2852
29
对,这个问题如果需要in place的话,跟BFS主要的区别就是不能光dequeue,得知道de
queue出来的这个结点在哪层,是否需要新建linkedlist。怎么能知道?

【在 j*****o 的大作中提到】
: 我amazon onsite考过这题
: 可以O(n)时间 O(1)空间的。
: 用2个指针,一个指着 i层,一个指着 i+1层这样子。(当然另外还要指针)
: 就是 i 层指针从左到右跑的时候把 i+1 层的全连好了。
: 不知说清楚没有><

c********t
发帖数: 5706
30
我现在说的不是这道题啊,是说怎么一次遍历按层打印一个btree,结点没有next, 没
有tail。怎么判断什么时候是处理完了一层?
当然如果有这种方法,这题也同层打印一样了。

【在 l*****a 的大作中提到】
: 我认为能,你怎么看?
: 你每次处理完一层,记录下tail就可以了,每次处理到这里,就知道一层结束了

相关主题
狗电面问道G家的面试题。
T第二轮面经MS on-site 面经&求分析(口头offer)
一道面试题binary tree的in-order iterator怎么写?
进入JobHunting版参与讨论
c********t
发帖数: 5706
31
同上文。

【在 K*********n 的大作中提到】
: 不要用recursion,用queue
: Node cur = root;
: q.enqueue(cur);
: while(!q.isEmpty()){
: cur = q.dequeue();
: System.out.println(cur.data);
: if (cur.left != null)
: q.enqueue(cur.left);
: if (crur.right != null)
: q.enqueue(cur.right);

K*********n
发帖数: 2852
32
最简单的是在Node里面加一个field: int level
还可以维护一个变量,记下每层的结点数,但是这个很麻烦
还可以用一个指针,指向每层最后一个结点。

【在 c********t 的大作中提到】
: 同上文。
c********t
发帖数: 5706
33
这个同意,如果不加的话。我那个层打印codes不能再优化了吧?

【在 K*********n 的大作中提到】
: 最简单的是在Node里面加一个field: int level
: 还可以维护一个变量,记下每层的结点数,但是这个很麻烦
: 还可以用一个指针,指向每层最后一个结点。

K*********n
发帖数: 2852
34
看来得用两个指针,指向每层最后一个节点,在enqueue的时候更新。比如:
1
2 3
4 5 6
假如这个指针叫levelEnd1,一开始指向1,然后在enqueue 1的孩子的时候,它先指向2
,再指向3。
然后在dequeue的时候,先dequeue 2,然后enqueue 2的孩子,另一个指针levelEnd2指
向4,然后5,然后dequeue 3,然后levelEnd2指向6,然后没了,因为3没有右子树。怎
么知道levelEnd2指向第三层的最后一个节点呢?用levelEnd1判断。因为levelEnd1指向
第二层最后一个,也就是3,所以他的孩子levelEnd2就是第三层最后一个。
然后,levelEnd1 = levelEnd2,第三层搞定。levelEnd2重置为null,然后去用做第四
层……
我觉得这个方法好,因为给Node加field有点赖皮,而且有可能不被允许。

【在 c********t 的大作中提到】
: 这个同意,如果不加的话。我那个层打印codes不能再优化了吧?
l*****a
发帖数: 14598
35
sigh
告诉你的方法你不认可。。。
你还接着问

【在 c********t 的大作中提到】
: 这个同意,如果不加的话。我那个层打印codes不能再优化了吧?
g**x
发帖数: 373
36
What is sibling node in Binary Tree?

【在 c********t 的大作中提到】
: 我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
: 存进去,第二遍再把每个list里的nodes连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

c********t
发帖数: 5706
37
唉,青蛙理解力弱,不知道tail在哪里啊。能给个codes吗?pseudo也行啊。

【在 l*****a 的大作中提到】
: sigh
: 告诉你的方法你不认可。。。
: 你还接着问

K*********n
发帖数: 2852
38
看我的帖,可以维护tail

【在 c********t 的大作中提到】
: 唉,青蛙理解力弱,不知道tail在哪里啊。能给个codes吗?pseudo也行啊。
c********t
发帖数: 5706
39
赞,明白了。

向2
指向

【在 K*********n 的大作中提到】
: 看来得用两个指针,指向每层最后一个节点,在enqueue的时候更新。比如:
: 1
: 2 3
: 4 5 6
: 假如这个指针叫levelEnd1,一开始指向1,然后在enqueue 1的孩子的时候,它先指向2
: ,再指向3。
: 然后在dequeue的时候,先dequeue 2,然后enqueue 2的孩子,另一个指针levelEnd2指
: 向4,然后5,然后dequeue 3,然后levelEnd2指向6,然后没了,因为3没有右子树。怎
: 么知道levelEnd2指向第三层的最后一个节点呢?用levelEnd1判断。因为levelEnd1指向
: 第二层最后一个,也就是3,所以他的孩子levelEnd2就是第三层最后一个。

b***e
发帖数: 1419
40
void _linkNext(Tree root) {
Tree parent = root.parent;

if (root == parent.left && parent.right) {
root.sibling = parent.right;
return;
}
Tree uncle = parent.sibling;
while (uncle && !uncle.left && !uncle.right) {
uncle = uncle.sibling;
}
if (!uncle) {
root.sibling = null;
return;
}
if (uncle.left) {
root.sibling = uncle.left;
return;
}
root.sibling = uncle.right;
}
void linkNext(Tree root) {
if (!root) {
return;
}

if (!root.parent) {
root.sibling = null;
return;
}
_linkNext(root);
linkNext(root.right);
linkNext(root.left);
}

【在 c********t 的大作中提到】
: 我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
: 存进去,第二遍再把每个list里的nodes连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

相关主题
binary tree的in-order iterator怎么写?一个老题binary tree找 lowest common ancestor 的code (请教
这个check whether a binary tree is a BST 问题讨论Amazon的一道题:根节点到叶节点之间最小和,并打印路径
A家,link all node in the same lev生成树
进入JobHunting版参与讨论
e******o
发帖数: 757
41
sibling怎么定义
是把同一层的node连起来么?
还是就是把同一个node的left 和 right 连起来。
如果是同一层连起来,root那一层是不是默认已经连起来了。

【在 c********t 的大作中提到】
: 我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
: 存进去,第二遍再把每个list里的nodes连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

w***o
发帖数: 109
42
来一个java的。space是O(1),复杂度应该是O(n)。
两个指针,一个current level的cur,一个是下一层link的头-nexthead:
void linkSibling(Node root)
Node cur = root;
Node nexthead = null;
while(cur != null) {
nexthead = null;
while(cur != null) {
Node runner = null;
if(cur.left != null) {
if(nexthead == null) {
nexthead = cur.left;
runner = nexthead;
} else {
runner.sibling = cur.left;
runner = runner.sibling;
}
}

if(cur.right != null) {
if(nexthead == null) {
nexthead = cur.right;
runner = nexthead;
} else {
runner.sibling = cur.right;
runner = runner.sibling;
}
}

cur = cur.sibling;
}
cur = nexthead;
}
i**********e
发帖数: 1145
43
这道题挺有意思的,我刚加上 OJ 了。
测了这里的所有程序,二爷的和 wwwyhx 的代码是正确的。
c*********t
发帖数: 2921
44
这道题没有看懂。什么是binary tree里面的sibling?俺的理解是 sibling是同一个
parent下的节点,如果是这样的话,一个parent对多只有两个children,还要弄什么
sibling呀?
是不是要把同一层的节点放到一个list里就行了?

【在 c********t 的大作中提到】
: 我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
: 存进去,第二遍再把每个list里的nodes连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

h****n
发帖数: 1093
45
不需要vector吧,假设binary tree是complete binary tree
已通过online judge测试
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root==NULL) return;
TreeLinkNode * cur = root;
TreeLinkNode * nextHead = cur->left;
for(;;)
{
//Reach the end of current level
if(cur==NULL)
{
//if there is a level in the next level
//Update cur and nextHead
if(nextHead!=NULL)
{
cur = nextHead;
nextHead = cur->left;
}
else break;
}
else
{
if(cur->left)
{
cur->left->next = cur->right;
}
if(cur->right)
{
if(cur->next)
{
cur->right->next = cur->next->left;
}
else cur->right->next = NULL;
}
cur = cur->next;
}
}
}
};

【在 b***m 的大作中提到】
: 说得很清楚了,基本就是这么做的。遍历某一层时,把下一层保存到一个queue或者
: vector中。

h****n
发帖数: 1093
46
分层用BFS也能做到,需要加两个counter
一个counter记录下一个level的数目,一个counter维护目前level已经遍历过的数目

【在 c********t 的大作中提到】
: 你说用queue? 那就是breadth frst travel吧。。
: 我可能没说清楚,我觉得breadth first travel不能做到分层,只能做到遍历啊
: 比如我想要的打印结果如下,是分层的
: 1
: 2 3
: 4 5 6
: 你说的方法能做到吗?
:
: tail

h****n
发帖数: 1093
47
没看到啊

【在 i**********e 的大作中提到】
: 这道题挺有意思的,我刚加上 OJ 了。
: 测了这里的所有程序,二爷的和 wwwyhx 的代码是正确的。

i**********e
发帖数: 1145
48
Populating Next Right Pointers in Each Node I & II.
http://www.leetcode.com/onlinejudge
如果有人还没看懂题目请提出来。

【在 h****n 的大作中提到】
: 没看到啊
j********x
发帖数: 2330
49
你没看懂他的意思
是本层的sibling顺序遍历,直接连好下一层,不需要额外保存任何东西,而且更加简洁

【在 b***m 的大作中提到】
: 说得很清楚了,基本就是这么做的。遍历某一层时,把下一层保存到一个queue或者
: vector中。

m*****k
发帖数: 731
50
不好意思,谁能解释一下题意啊,
input:
1

2
/ 、
3 4

5
啥是output啊?
相关主题
做了一下merge BST今天面的太惨了....
攒人品,Twitter 电面题目很可能被这题搞挂了,sort linked list
贡献一道G家的onsite题和简单面经(已悲剧)请问如何sort一个linked list?
进入JobHunting版参与讨论
c********t
发帖数: 5706
51
我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
存进去,第二遍再把每个list里的nodes连起来
记得这道题前一阵讨论过,谁能帮我找到。
g**e
发帖数: 6127
52
跟按层打印node没分别吧

【在 c********t 的大作中提到】
: 我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
: 存进去,第二遍再把每个list里的nodes连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

c********t
发帖数: 5706
53
还是有分别的,层打印很多节点要走多遍

【在 g**e 的大作中提到】
: 跟按层打印node没分别吧
j*****o
发帖数: 394
54
我amazon onsite考过这题
可以O(n)时间 O(1)空间的。
用2个指针,一个指着 i层,一个指着 i+1层这样子。(当然另外还要指针)
就是 i 层指针从左到右跑的时候把 i+1 层的全连好了。
不知说清楚没有><

【在 c********t 的大作中提到】
: 我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
: 存进去,第二遍再把每个list里的nodes连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

b***m
发帖数: 5987
55
说得很清楚了,基本就是这么做的。遍历某一层时,把下一层保存到一个queue或者
vector中。

【在 j*****o 的大作中提到】
: 我amazon onsite考过这题
: 可以O(n)时间 O(1)空间的。
: 用2个指针,一个指着 i层,一个指着 i+1层这样子。(当然另外还要指针)
: 就是 i 层指针从左到右跑的时候把 i+1 层的全连好了。
: 不知说清楚没有><

w****x
发帖数: 2483
56
/*
add sibling pointer to the right sibling of each node in a tree, O(n) time,
O(1) space.
5 minutes thinking, 10 minutes coding, a hint he gave me: recursion
*/
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE* pSibling;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL), pSibling(NULL) {}
};
void LinkRightFromParent(NODE* pNode, NODE* pParent)
{
if (pNode == NULL) return;
//Under this situation, the current node will connect to the child of
current parent
if (pParent != NULL && pParent->pLft == pNode && pParent->pRgt != NULL)
pNode->pSibling = pParent->pRgt;
else //pitfall: when starting from parent chain search, should start at
//the next node to the parent. E.g, if a parent got a left child
and
//right child, and the current node is right child, then the right
child
//will connect to the left child, then dead loop!!!!
{
NODE* pIter = pParent == NULL ? NULL : pParent->pSibling;
//logic below is to find the next right node by parent chain
NODE* pRgtCon = NULL;
while (pIter != NULL && pRgtCon == NULL)
{
if (pIter->pLft != NULL)
pRgtCon = pIter->pLft;
else if (pIter->pRgt != NULL)
pRgtCon = pIter->pRgt;
pIter = pIter->pSibling;
}
pNode->pSibling = pRgtCon;
}
LinkRightFromParent(pNode->pRgt, pNode);
LinkRightFromParent(pNode->pLft, pNode);
}
c********t
发帖数: 5706
57
明白了,我是你这个思路,但是中间存的太多,看来很多余。我试试你的,多谢。

【在 j*****o 的大作中提到】
: 我amazon onsite考过这题
: 可以O(n)时间 O(1)空间的。
: 用2个指针,一个指着 i层,一个指着 i+1层这样子。(当然另外还要指针)
: 就是 i 层指针从左到右跑的时候把 i+1 层的全连好了。
: 不知说清楚没有><

p*****2
发帖数: 21240
58

,
这题感觉BFS逻辑简单很多吧。你面试要求DFS做?

【在 w****x 的大作中提到】
: /*
: add sibling pointer to the right sibling of each node in a tree, O(n) time,
: O(1) space.
: 5 minutes thinking, 10 minutes coding, a hint he gave me: recursion
: */
: struct NODE
: {
: int nVal;
: NODE* pLft;
: NODE* pRgt;

p*****2
发帖数: 21240
59

他说的是O(1) space, 不用queue。

【在 b***m 的大作中提到】
: 说得很清楚了,基本就是这么做的。遍历某一层时,把下一层保存到一个queue或者
: vector中。

p*****2
发帖数: 21240
60

为什么?

【在 c********t 的大作中提到】
: 还是有分别的,层打印很多节点要走多遍
相关主题
Populating Next Right Pointers in Each Node IIT第二轮面经
发几个面试题一道面试题
狗电面问道G家的面试题。
进入JobHunting版参与讨论
p*****2
发帖数: 21240
61
我写了一个,有点繁琐,还没测试。
void connectSibling(Node root)
{
assert(root!=null);

Node curr=root;

while(curr!=null)
{
Node prev=null;
Node next=null;

while(curr!=null)
{
if(curr.left!=null)
{
if(prev==null)
{
prev=curr.left;
next=prev;
}
else
{
prev.sibling=curr.left;
prev=prev.sibling;
}
}

if(curr.right!=null)
{
if(prev==null)
{
prev=curr.right;
next=prev;
}
else
{
prev.sibling=curr.right;
prev=prev.sibling;
}
}

curr=curr.sibling;
}
curr=next;
}
}
w****x
发帖数: 2483
62

这题印象很深刻啊, 先上BFS再上DFS

【在 p*****2 的大作中提到】
: 我写了一个,有点繁琐,还没测试。
: void connectSibling(Node root)
: {
: assert(root!=null);
:
: Node curr=root;
:
: while(curr!=null)
: {
: Node prev=null;

b***m
发帖数: 5987
63

哦,对,我没仔细看。

【在 p*****2 的大作中提到】
: 我写了一个,有点繁琐,还没测试。
: void connectSibling(Node root)
: {
: assert(root!=null);
:
: Node curr=root;
:
: while(curr!=null)
: {
: Node prev=null;

p*****2
发帖数: 21240
64

这样呀。 DFS一定先搞右边再搞左边吧。一会儿写一个。

【在 w****x 的大作中提到】
:
: 这题印象很深刻啊, 先上BFS再上DFS

l*****a
发帖数: 14598
65
太繁琐
直接让回家

【在 p*****2 的大作中提到】
: 我写了一个,有点繁琐,还没测试。
: void connectSibling(Node root)
: {
: assert(root!=null);
:
: Node curr=root;
:
: while(curr!=null)
: {
: Node prev=null;

p*****2
发帖数: 21240
66
写了一个DFS的
Node findNext(Node node)
{
if(node==null)
return null;

while(node!=null)
{
if(node.left!=null)
return node.left;
if(node.right!=null)
return node.right;

node=node.sibling;
}

return null;
}

void dfs(Node node, Node parent)
{
if(node==null)
return;

if(node==parent.left && parent.right!=null)
{
node.sibling=parent.right;
}
else
{
node.sibling=findNext(parent.sibling);
}

dfs(node.right,node);
dfs(node.left,node);
}

void connectSibling(Node root)
{
assert(root!=null);
dfs(root.right,root);
dfs(root.left,root);
}
l*****a
发帖数: 14598
67
find next复杂度多少?
每个node再求一遍next
感觉复杂度太高了

【在 p*****2 的大作中提到】
: 写了一个DFS的
: Node findNext(Node node)
: {
: if(node==null)
: return null;
:
: while(node!=null)
: {
: if(node.left!=null)
: return node.left;

l*****a
发帖数: 14598
68
一个dummy node,指的都是现有node,并不消费额外空间

【在 c********t 的大作中提到】
: 明白了,我是你这个思路,但是中间存的太多,看来很多余。我试试你的,多谢。
p*****2
发帖数: 21240
69

findnext一般很快就退出了吧?如果都没有children的话,也就被多扫一边。

【在 l*****a 的大作中提到】
: find next复杂度多少?
: 每个node再求一遍next
: 感觉复杂度太高了

l*****a
发帖数: 14598
70
复杂度不能用很快描述吧?
肯定是1 or n 相关啊

【在 p*****2 的大作中提到】
:
: findnext一般很快就退出了吧?如果都没有children的话,也就被多扫一边。

相关主题
问道G家的面试题。这个check whether a binary tree is a BST 问题
MS on-site 面经&求分析(口头offer)A家,link all node in the same lev
binary tree的in-order iterator怎么写?一个老题binary tree找 lowest common ancestor 的code (请教
进入JobHunting版参与讨论
p*****2
发帖数: 21240
71

你觉得不是O(n)吗?

【在 l*****a 的大作中提到】
: 复杂度不能用很快描述吧?
: 肯定是1 or n 相关啊

l*****a
发帖数: 14598
72
不认为。
元芳,你怎么看? ==> to wwwyhx

【在 p*****2 的大作中提到】
:
: 你觉得不是O(n)吗?

c********t
发帖数: 5706
73
你如果说的是 breadth first travel, 是用queue走一遍,但没法做到分层
如果是层打印,我只会写以下代码,不但需要多次access nodes,还要先求高度。你有
什么办法一次遍历层打印吗?多谢。
public void printLevelOrder() {
for (int i = 1; i <= this.maxHeight(); i++) {
printLevel(this, i);
System.out.println();
}
}
public void printLevel(Node node, int level) {
if (node == null)
return;
if (level == 1)
System.out.print(node.value + " ");
else {
printLevel(node.left, level - 1);
printLevel(node.right, level - 1);
}
}


【在 p*****2 的大作中提到】
:
: 你觉得不是O(n)吗?

l*****a
发帖数: 14598
74
user Vector/ArrayList之类的咚咚
每次print First item ,remove from head and insert its children into the tail
of the structure.

【在 c********t 的大作中提到】
: 你如果说的是 breadth first travel, 是用queue走一遍,但没法做到分层
: 如果是层打印,我只会写以下代码,不但需要多次access nodes,还要先求高度。你有
: 什么办法一次遍历层打印吗?多谢。
: public void printLevelOrder() {
: for (int i = 1; i <= this.maxHeight(); i++) {
: printLevel(this, i);
: System.out.println();
: }
: }
: public void printLevel(Node node, int level) {

c********t
发帖数: 5706
75
你说用queue? 那就是breadth frst travel吧。。
我可能没说清楚,我觉得breadth first travel不能做到分层,只能做到遍历啊
比如我想要的打印结果如下,是分层的
1
2 3
4 5 6
你说的方法能做到吗?

tail

【在 l*****a 的大作中提到】
: user Vector/ArrayList之类的咚咚
: 每次print First item ,remove from head and insert its children into the tail
: of the structure.

x*****n
发帖数: 195
76
不错!i层已经被link到一起了,挨个扫描和处理i+1层的nodes就行。

【在 b***m 的大作中提到】
: 说得很清楚了,基本就是这么做的。遍历某一层时,把下一层保存到一个queue或者
: vector中。

l*****a
发帖数: 14598
77
我认为能,你怎么看?
你每次处理完一层,记录下tail就可以了,每次处理到这里,就知道一层结束了

【在 c********t 的大作中提到】
: 你说用queue? 那就是breadth frst travel吧。。
: 我可能没说清楚,我觉得breadth first travel不能做到分层,只能做到遍历啊
: 比如我想要的打印结果如下,是分层的
: 1
: 2 3
: 4 5 6
: 你说的方法能做到吗?
:
: tail

K*********n
发帖数: 2852
78
不要用recursion,用queue
Node cur = root;
q.enqueue(cur);
while(!q.isEmpty()){
cur = q.dequeue();
System.out.println(cur.data);
if (cur.left != null)
q.enqueue(cur.left);
if (crur.right != null)
q.enqueue(cur.right);
}

【在 c********t 的大作中提到】
: 你如果说的是 breadth first travel, 是用queue走一遍,但没法做到分层
: 如果是层打印,我只会写以下代码,不但需要多次access nodes,还要先求高度。你有
: 什么办法一次遍历层打印吗?多谢。
: public void printLevelOrder() {
: for (int i = 1; i <= this.maxHeight(); i++) {
: printLevel(this, i);
: System.out.println();
: }
: }
: public void printLevel(Node node, int level) {

K*********n
发帖数: 2852
79
对,这个问题如果需要in place的话,跟BFS主要的区别就是不能光dequeue,得知道de
queue出来的这个结点在哪层,是否需要新建linkedlist。怎么能知道?

【在 j*****o 的大作中提到】
: 我amazon onsite考过这题
: 可以O(n)时间 O(1)空间的。
: 用2个指针,一个指着 i层,一个指着 i+1层这样子。(当然另外还要指针)
: 就是 i 层指针从左到右跑的时候把 i+1 层的全连好了。
: 不知说清楚没有><

c********t
发帖数: 5706
80
我现在说的不是这道题啊,是说怎么一次遍历按层打印一个btree,结点没有next, 没
有tail。怎么判断什么时候是处理完了一层?
当然如果有这种方法,这题也同层打印一样了。

【在 l*****a 的大作中提到】
: 我认为能,你怎么看?
: 你每次处理完一层,记录下tail就可以了,每次处理到这里,就知道一层结束了

相关主题
讨论Amazon的一道题:根节点到叶节点之间最小和,并打印路径攒人品,Twitter 电面题目
生成树贡献一道G家的onsite题和简单面经(已悲剧)
做了一下merge BST今天面的太惨了....
进入JobHunting版参与讨论
c********t
发帖数: 5706
81
同上文。

【在 K*********n 的大作中提到】
: 不要用recursion,用queue
: Node cur = root;
: q.enqueue(cur);
: while(!q.isEmpty()){
: cur = q.dequeue();
: System.out.println(cur.data);
: if (cur.left != null)
: q.enqueue(cur.left);
: if (crur.right != null)
: q.enqueue(cur.right);

K*********n
发帖数: 2852
82
最简单的是在Node里面加一个field: int level
还可以维护一个变量,记下每层的结点数,但是这个很麻烦
还可以用一个指针,指向每层最后一个结点。

【在 c********t 的大作中提到】
: 同上文。
c********t
发帖数: 5706
83
这个同意,如果不加的话。我那个层打印codes不能再优化了吧?

【在 K*********n 的大作中提到】
: 最简单的是在Node里面加一个field: int level
: 还可以维护一个变量,记下每层的结点数,但是这个很麻烦
: 还可以用一个指针,指向每层最后一个结点。

K*********n
发帖数: 2852
84
看来得用两个指针,指向每层最后一个节点,在enqueue的时候更新。比如:
1
2 3
4 5 6
假如这个指针叫levelEnd1,一开始指向1,然后在enqueue 1的孩子的时候,它先指向2
,再指向3。
然后在dequeue的时候,先dequeue 2,然后enqueue 2的孩子,另一个指针levelEnd2指
向4,然后5,然后dequeue 3,然后levelEnd2指向6,然后没了,因为3没有右子树。怎
么知道levelEnd2指向第三层的最后一个节点呢?用levelEnd1判断。因为levelEnd1指向
第二层最后一个,也就是3,所以他的孩子levelEnd2就是第三层最后一个。
然后,levelEnd1 = levelEnd2,第三层搞定。levelEnd2重置为null,然后去用做第四
层……
我觉得这个方法好,因为给Node加field有点赖皮,而且有可能不被允许。

【在 c********t 的大作中提到】
: 这个同意,如果不加的话。我那个层打印codes不能再优化了吧?
l*****a
发帖数: 14598
85
sigh
告诉你的方法你不认可。。。
你还接着问

【在 c********t 的大作中提到】
: 这个同意,如果不加的话。我那个层打印codes不能再优化了吧?
g**x
发帖数: 373
86
What is sibling node in Binary Tree?

【在 c********t 的大作中提到】
: 我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
: 存进去,第二遍再把每个list里的nodes连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

c********t
发帖数: 5706
87
唉,青蛙理解力弱,不知道tail在哪里啊。能给个codes吗?pseudo也行啊。

【在 l*****a 的大作中提到】
: sigh
: 告诉你的方法你不认可。。。
: 你还接着问

K*********n
发帖数: 2852
88
看我的帖,可以维护tail

【在 c********t 的大作中提到】
: 唉,青蛙理解力弱,不知道tail在哪里啊。能给个codes吗?pseudo也行啊。
c********t
发帖数: 5706
89
赞,明白了。

向2
指向

【在 K*********n 的大作中提到】
: 看来得用两个指针,指向每层最后一个节点,在enqueue的时候更新。比如:
: 1
: 2 3
: 4 5 6
: 假如这个指针叫levelEnd1,一开始指向1,然后在enqueue 1的孩子的时候,它先指向2
: ,再指向3。
: 然后在dequeue的时候,先dequeue 2,然后enqueue 2的孩子,另一个指针levelEnd2指
: 向4,然后5,然后dequeue 3,然后levelEnd2指向6,然后没了,因为3没有右子树。怎
: 么知道levelEnd2指向第三层的最后一个节点呢?用levelEnd1判断。因为levelEnd1指向
: 第二层最后一个,也就是3,所以他的孩子levelEnd2就是第三层最后一个。

b***e
发帖数: 1419
90
void _linkNext(Tree root) {
Tree parent = root.parent;

if (root == parent.left && parent.right) {
root.sibling = parent.right;
return;
}
Tree uncle = parent.sibling;
while (uncle && !uncle.left && !uncle.right) {
uncle = uncle.sibling;
}
if (!uncle) {
root.sibling = null;
return;
}
if (uncle.left) {
root.sibling = uncle.left;
return;
}
root.sibling = uncle.right;
}
void linkNext(Tree root) {
if (!root) {
return;
}

if (!root.parent) {
root.sibling = null;
return;
}
_linkNext(root);
linkNext(root.right);
linkNext(root.left);
}

【在 c********t 的大作中提到】
: 我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
: 存进去,第二遍再把每个list里的nodes连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

相关主题
很可能被这题搞挂了,sort linked list发几个面试题
请问如何sort一个linked list?狗电面
Populating Next Right Pointers in Each Node IIT第二轮面经
进入JobHunting版参与讨论
e******o
发帖数: 757
91
sibling怎么定义
是把同一层的node连起来么?
还是就是把同一个node的left 和 right 连起来。
如果是同一层连起来,root那一层是不是默认已经连起来了。

【在 c********t 的大作中提到】
: 我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
: 存进去,第二遍再把每个list里的nodes连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

w***o
发帖数: 109
92
来一个java的。space是O(1),复杂度应该是O(n)。
两个指针,一个current level的cur,一个是下一层link的头-nexthead:
void linkSibling(Node root)
Node cur = root;
Node nexthead = null;
while(cur != null) {
nexthead = null;
while(cur != null) {
Node runner = null;
if(cur.left != null) {
if(nexthead == null) {
nexthead = cur.left;
runner = nexthead;
} else {
runner.sibling = cur.left;
runner = runner.sibling;
}
}

if(cur.right != null) {
if(nexthead == null) {
nexthead = cur.right;
runner = nexthead;
} else {
runner.sibling = cur.right;
runner = runner.sibling;
}
}

cur = cur.sibling;
}
cur = nexthead;
}
i**********e
发帖数: 1145
93
这道题挺有意思的,我刚加上 OJ 了。
测了这里的所有程序,二爷的和 wwwyhx 的代码是正确的。
c*********t
发帖数: 2921
94
这道题没有看懂。什么是binary tree里面的sibling?俺的理解是 sibling是同一个
parent下的节点,如果是这样的话,一个parent对多只有两个children,还要弄什么
sibling呀?
是不是要把同一层的节点放到一个list里就行了?

【在 c********t 的大作中提到】
: 我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
: 存进去,第二遍再把每个list里的nodes连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

h****n
发帖数: 1093
95
不需要vector吧,假设binary tree是complete binary tree
已通过online judge测试
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root==NULL) return;
TreeLinkNode * cur = root;
TreeLinkNode * nextHead = cur->left;
for(;;)
{
//Reach the end of current level
if(cur==NULL)
{
//if there is a level in the next level
//Update cur and nextHead
if(nextHead!=NULL)
{
cur = nextHead;
nextHead = cur->left;
}
else break;
}
else
{
if(cur->left)
{
cur->left->next = cur->right;
}
if(cur->right)
{
if(cur->next)
{
cur->right->next = cur->next->left;
}
else cur->right->next = NULL;
}
cur = cur->next;
}
}
}
};

【在 b***m 的大作中提到】
: 说得很清楚了,基本就是这么做的。遍历某一层时,把下一层保存到一个queue或者
: vector中。

h****n
发帖数: 1093
96
分层用BFS也能做到,需要加两个counter
一个counter记录下一个level的数目,一个counter维护目前level已经遍历过的数目

【在 c********t 的大作中提到】
: 你说用queue? 那就是breadth frst travel吧。。
: 我可能没说清楚,我觉得breadth first travel不能做到分层,只能做到遍历啊
: 比如我想要的打印结果如下,是分层的
: 1
: 2 3
: 4 5 6
: 你说的方法能做到吗?
:
: tail

h****n
发帖数: 1093
97
没看到啊

【在 i**********e 的大作中提到】
: 这道题挺有意思的,我刚加上 OJ 了。
: 测了这里的所有程序,二爷的和 wwwyhx 的代码是正确的。

i**********e
发帖数: 1145
98
Populating Next Right Pointers in Each Node I & II.
http://www.leetcode.com/onlinejudge
如果有人还没看懂题目请提出来。

【在 h****n 的大作中提到】
: 没看到啊
j********x
发帖数: 2330
99
你没看懂他的意思
是本层的sibling顺序遍历,直接连好下一层,不需要额外保存任何东西,而且更加简洁

【在 b***m 的大作中提到】
: 说得很清楚了,基本就是这么做的。遍历某一层时,把下一层保存到一个queue或者
: vector中。

m*****k
发帖数: 731
100
不好意思,谁能解释一下题意啊,
input:
1

2
/ 、
3 4

5
啥是output啊?
相关主题
一道面试题binary tree的in-order iterator怎么写?
问道G家的面试题。这个check whether a binary tree is a BST 问题
MS on-site 面经&求分析(口头offer)A家,link all node in the same lev
进入JobHunting版参与讨论
s******o
发帖数: 328
101
inline void connectOne( Node *n, Node *&nHead, Node *&nTmp ) {
if ( n == NULL ) return;
if ( nHead == NULL ) { nHead = nTmp = n; }
else { nTmp->next = n; nTmp = nTmp->next; }
}
void connect(Node *root) {
Node * cHead = root;
while ( cHead != NULL ) {
Node * nHead = NULL, * nTmp = NULL, *cTmp = cHead;
while ( cTmp != NULL ) {
connectOne( cTmp->left, nHead, nTmp );
connectOne( cTmp->right, nHead, nTmp );
cTmp = cTmp->next;
}
cHead = nHead;
}
}
d*******u
发帖数: 186
102
BFS, Queue, 按层打印。

【在 c********t 的大作中提到】
: 我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
: 存进去,第二遍再把每个list里的nodes连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

p*****2
发帖数: 21240
103

这题用queue就WS了吧?

【在 d*******u 的大作中提到】
: BFS, Queue, 按层打印。
c****7
发帖数: 13
104
我也整了个, 请大家提提意见。
public static void connect1(TreeLinkNode root) {
if (root==null)
return;
// index variable for the current level
TreeLinkNode curLevNode = root;
// scan the tree node level by level
while(curLevNode!=null){
// index variable for the next level,
// which is used to connect with previous sibling node
TreeLinkNode nxtLevPreNode=null;// initialize as null
// the first node of the next level, (which will
// be passed to connect() for recursive invoke)
TreeLinkNode firstNxtLevNode=null; // initialize as null
// while scanning all the node in the current level,
// connect the nodes in the next level by setting its next field
while(curLevNode!=null){
// get the leftChild and rightChild of the current node
TreeLinkNode leftChild = curLevNode.left;
TreeLinkNode rightChild = curLevNode.right;
// if the current node has a leftChild
if(leftChild!=null){
// if nxtLevPreNode is null, then the leftChild
// would be the first node in the next level
if(nxtLevPreNode==null)
firstNxtLevNode = leftChild;
else// connect with previous sibling node
nxtLevPreNode.next = leftChild;
// update nxtLevPreNode
nxtLevPreNode = leftChild;
}
// if the current node has a rightChild
if (rightChild!=null){
// if nxtLevPreNode is null, then the rightChild
// would be the first node in the next level
if(nxtLevPreNode==null)
firstNxtLevNode = rightChild;
else// connect with previous sibling node
nxtLevPreNode.next = rightChild;
// update nxtLevPreNode
nxtLevPreNode = rightChild;
}
// move the next node of current level
curLevNode = curLevNode.next;
}// end of while
// move to next level
curLevNode = firstNxtLevNode;
}
}
t********y
发帖数: 14
105
adding a null to the end of each level can be helpful. following is printing
out each level. making link list is just same, creating a new list each
time a null is Dequeued. Tail null is taken care automatically.
public void PrintOutLevel(TreeNode node)
{
// null,check.....
Queue q = new Queue();
q.Enqueue(node);
q.Enqueue(null); // This is the tail of the first levle.
while (!(q.Count == 0))
{
TreeNode tmp = q.Dequeue();
if (tmp == null)
{
//print out new line...
if (!(q.Count == 0)) // make sure the null is not the
tail of the last level.
{
q.Enqueue(null); // tail of the level.
}
continue;
}
if (tmp.LeftChild != null) q.Enqueue(tmp.LeftChild);
if (tmp.RightChild != null) q.Enqueue(tmp.RightChild);
}
}
l*****a
发帖数: 559
106
赞。

【在 c****7 的大作中提到】
: 我也整了个, 请大家提提意见。
: public static void connect1(TreeLinkNode root) {
: if (root==null)
: return;
: // index variable for the current level
: TreeLinkNode curLevNode = root;
: // scan the tree node level by level
: while(curLevNode!=null){
: // index variable for the next level,
: // which is used to connect with previous sibling node

p********2
发帖数: 123
107
感觉不复杂,就bfs完了
java版过了OJ
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null) return;
TreeLinkNode cur=root;
Queue q=new LinkedList();
q.add(cur);

while(!q.isEmpty()){
cur=q.remove();
if(cur.left!=null){
q.add(cur.left);
cur.left.next=cur.right;
}
if(cur.right!=null){
q.add(cur.right);
if(cur.next!=null){
cur.right.next=cur.next.left;
}
}}}}
h*******n
发帖数: 4
108


【在 i**********e 的大作中提到】
: 这道题挺有意思的,我刚加上 OJ 了。
: 测了这里的所有程序,二爷的和 wwwyhx 的代码是正确的。

w****a
发帖数: 710
109
这个就是BFS吧?next指向右边的节点。
LEETCODE有
1 (共1页)
进入JobHunting版参与讨论
相关主题
Populating Next Right Pointers in Each Node II这个check whether a binary tree is a BST 问题
发几个面试题A家,link all node in the same lev
狗电面一个老题binary tree找 lowest common ancestor 的code (请教
T第二轮面经讨论Amazon的一道题:根节点到叶节点之间最小和,并打印路径
一道面试题生成树
问道G家的面试题。做了一下merge BST
MS on-site 面经&求分析(口头offer)攒人品,Twitter 电面题目
binary tree的in-order iterator怎么写?贡献一道G家的onsite题和简单面经(已悲剧)
相关话题的讨论汇总
话题: null话题: node话题: cur话题: root话题: nexthead