Redian新闻
>
Discover给的那个FICO分数是真的还是模拟的?
avatar
Discover给的那个FICO分数是真的还是模拟的?# Money - 海外理财
c*t
1
我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
存进去,第二遍再把每个list里的nodes连起来
记得这道题前一阵讨论过,谁能帮我找到。
avatar
c*n
2
NEW! Discover is now providing your FICO® Credit Score for free. View
Now.
就在statement页面中间……
这个是实时更新的么,或者多久更新一次?是真的FICO分数还是像CreditKarma那样的
模拟分啊?
而且根据FAQ,这个分数来自TU的……同样来自TU,creditkarma给我720,discover给
我770……这也差太多了……
avatar
g*e
3
跟按层打印node没分别吧

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

avatar
T*2
4
是真的 一个月更新一次
avatar
c*t
5
还是有分别的,层打印很多节点要走多遍

【在 g**e 的大作中提到】
: 跟按层打印node没分别吧
avatar
i*g
6
我的一个754 一个752。。

【在 c*******n 的大作中提到】
: NEW! Discover is now providing your FICO® Credit Score for free. View
: Now.
: 就在statement页面中间……
: 这个是实时更新的么,或者多久更新一次?是真的FICO分数还是像CreditKarma那样的
: 模拟分啊?
: 而且根据FAQ,这个分数来自TU的……同样来自TU,creditkarma给我720,discover给
: 我770……这也差太多了……

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

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

avatar
k*u
8
我的800多,瓦咔咔,赶紧申请新卡。
avatar
b*m
9
说得很清楚了,基本就是这么做的。遍历某一层时,把下一层保存到一个queue或者
vector中。

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

avatar
w*x
10
/*
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);
}
avatar
c*t
11
明白了,我是你这个思路,但是中间存的太多,看来很多余。我试试你的,多谢。

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

avatar
p*2
12

,
这题感觉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;

avatar
p*2
13

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

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

avatar
p*2
14

为什么?

【在 c********t 的大作中提到】
: 还是有分别的,层打印很多节点要走多遍
avatar
p*2
15
我写了一个,有点繁琐,还没测试。
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++;
}
}
avatar
w*x
16

这题印象很深刻啊, 先上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)

avatar
b*m
17

哦,对,我没仔细看。

【在 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)

avatar
p*2
18

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

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

avatar
l*a
19
太繁琐
直接让回家

【在 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)

avatar
p*2
20
写了一个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);
}
avatar
l*a
21
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;

avatar
l*a
22
一个dummy node,指的都是现有node,并不消费额外空间

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

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

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

avatar
l*a
24
复杂度不能用很快描述吧?
肯定是1 or n 相关啊

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

avatar
p*2
25

你觉得不是O(n)吗?

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

avatar
l*a
26
不认为。
元芳,你怎么看? ==> to wwwyhx

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

avatar
c*t
27
你如果说的是 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)吗?

avatar
l*a
28
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) {

avatar
c*t
29
你说用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.

avatar
x*n
30
不错!i层已经被link到一起了,挨个扫描和处理i+1层的nodes就行。

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

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

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

avatar
K*n
32
不要用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) {

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

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

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

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

avatar
c*t
35
同上文。

【在 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);

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

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

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

avatar
K*n
38
看来得用两个指针,指向每层最后一个节点,在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不能再优化了吧?
avatar
l*a
39
sigh
告诉你的方法你不认可。。。
你还接着问

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

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

avatar
c*t
41
唉,青蛙理解力弱,不知道tail在哪里啊。能给个codes吗?pseudo也行啊。

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

avatar
K*n
42
看我的帖,可以维护tail

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

向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就是第三层最后一个。

avatar
b*e
44
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连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

avatar
e*o
45
sibling怎么定义
是把同一层的node连起来么?
还是就是把同一个node的left 和 right 连起来。
如果是同一层连起来,root那一层是不是默认已经连起来了。

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

avatar
w*o
46
来一个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;
}
avatar
i*e
47
这道题挺有意思的,我刚加上 OJ 了。
测了这里的所有程序,二爷的和 wwwyhx 的代码是正确的。
avatar
c*t
48
这道题没有看懂。什么是binary tree里面的sibling?俺的理解是 sibling是同一个
parent下的节点,如果是这样的话,一个parent对多只有两个children,还要弄什么
sibling呀?
是不是要把同一层的节点放到一个list里就行了?

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

avatar
h*n
49
不需要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中。

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

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

avatar
h*n
51
没看到啊

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

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

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

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

avatar
m*k
54
不好意思,谁能解释一下题意啊,
input:
1

2
/ 、
3 4

5
啥是output啊?
avatar
c*t
55
我写了一个,比较麻烦,用了List>结构,第一遍把每层nodes作为list全
存进去,第二遍再把每个list里的nodes连起来
记得这道题前一阵讨论过,谁能帮我找到。
avatar
g*e
56
跟按层打印node没分别吧

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

avatar
c*t
57
还是有分别的,层打印很多节点要走多遍

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

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

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

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

avatar
w*x
60
/*
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);
}
avatar
c*t
61
明白了,我是你这个思路,但是中间存的太多,看来很多余。我试试你的,多谢。

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

avatar
p*2
62

,
这题感觉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;

avatar
p*2
63

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

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

avatar
p*2
64

为什么?

【在 c********t 的大作中提到】
: 还是有分别的,层打印很多节点要走多遍
avatar
p*2
65
我写了一个,有点繁琐,还没测试。
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;
}
}
avatar
w*x
66

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

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

avatar
b*m
67

哦,对,我没仔细看。

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

avatar
p*2
68

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

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

avatar
l*a
69
太繁琐
直接让回家

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

avatar
p*2
70
写了一个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);
}
avatar
l*a
71
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;

avatar
l*a
72
一个dummy node,指的都是现有node,并不消费额外空间

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

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

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

avatar
l*a
74
复杂度不能用很快描述吧?
肯定是1 or n 相关啊

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

avatar
p*2
75

你觉得不是O(n)吗?

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

avatar
l*a
76
不认为。
元芳,你怎么看? ==> to wwwyhx

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

avatar
c*t
77
你如果说的是 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)吗?

avatar
l*a
78
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) {

avatar
c*t
79
你说用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.

avatar
x*n
80
不错!i层已经被link到一起了,挨个扫描和处理i+1层的nodes就行。

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

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

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

avatar
K*n
82
不要用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) {

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

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

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

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

avatar
c*t
85
同上文。

【在 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);

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

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

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

avatar
K*n
88
看来得用两个指针,指向每层最后一个节点,在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不能再优化了吧?
avatar
l*a
89
sigh
告诉你的方法你不认可。。。
你还接着问

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

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

avatar
c*t
91
唉,青蛙理解力弱,不知道tail在哪里啊。能给个codes吗?pseudo也行啊。

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

avatar
K*n
92
看我的帖,可以维护tail

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

向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就是第三层最后一个。

avatar
b*e
94
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连起来
: 记得这道题前一阵讨论过,谁能帮我找到。

avatar
e*o
95
sibling怎么定义
是把同一层的node连起来么?
还是就是把同一个node的left 和 right 连起来。
如果是同一层连起来,root那一层是不是默认已经连起来了。

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

avatar
w*o
96
来一个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;
}
avatar
i*e
97
这道题挺有意思的,我刚加上 OJ 了。
测了这里的所有程序,二爷的和 wwwyhx 的代码是正确的。
avatar
c*t
98
这道题没有看懂。什么是binary tree里面的sibling?俺的理解是 sibling是同一个
parent下的节点,如果是这样的话,一个parent对多只有两个children,还要弄什么
sibling呀?
是不是要把同一层的节点放到一个list里就行了?

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

avatar
h*n
99
不需要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中。

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

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

avatar
h*n
101
没看到啊

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

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

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

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

avatar
m*k
104
不好意思,谁能解释一下题意啊,
input:
1

2
/ 、
3 4

5
啥是output啊?
avatar
s*o
105
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;
}
}
avatar
d*u
106
BFS, Queue, 按层打印。

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

avatar
p*2
107

这题用queue就WS了吧?

【在 d*******u 的大作中提到】
: BFS, Queue, 按层打印。
avatar
c*7
108
我也整了个, 请大家提提意见。
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;
}
}
avatar
t*y
109
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);
}
}
avatar
l*a
110
赞。

【在 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

avatar
p*2
111
感觉不复杂,就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;
}
}}}}
avatar
h*n
112


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

avatar
w*a
113
这个就是BFS吧?next指向右边的节点。
LEETCODE有
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。