j*****y
发帖数: 1071 | 1 leetcode 上的这道题谁有简洁一些的代码阿？ 自己的写的有点惨不忍睹 | l**b
发帖数: 457 | 2 一样的啰嗦。
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) return;
connectLevel(null, root);
connect(getNext(root));
}
private TreeLinkNode getNext(TreeLinkNode last) {
if (last == null) return null;
if (last.left != null) return last.left;
if (last.right != null) return last.right;
return getNext(last.next);
}
private void connectLevel(TreeLinkNode last, TreeLinkNode p) {
if (p == null) return;
if (p.left == null && p.right == null) {
connectLevel(last, p.next);
} else if (p.left != null && p.right != null) {
if (last != null) last.next = p.left;
p.left.next = p.right;
connectLevel(p.right, p.next);
} else if (p.right == null) {
if (last != null) last.next = p.left;
connectLevel(p.left, p.next);
} else {
if (last != null) last.next = p.right;
connectLevel(p.right, p.next);
}
}
} | p*****2
发帖数: 21240 | | j*****y
发帖数: 1071 | 4 你这个用了 recursive感觉就不是 constant space了吧 ？
一样的啰嗦。
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) return;
connectLevel(null, root);
connect(getNext(root));
}
private TreeLinkNode getNext(TreeLinkNode last) {
if (last == null) return null;
if (last.left != null) return last.left;
if (last.right != null) return last.right;
return getNext(last.next);
}
private void connectLevel(TreeLinkNode last, TreeLinkNode p) {
if (p == null) return;
if (p.left == null && p.right == null) {
connectLevel(last, p.next);
} else if (p.left != null && p.right != null) {
if (last != null) last.next = p.left;
p.left.next = p.right;
connectLevel(p.right, p.next);
} else if (p.right == null) {
if (last != null) last.next = p.left;
connectLevel(p.left, p.next);
} else {
if (last != null) last.next = p.right;
connectLevel(p.right, p.next);
}
}
}
【在 l**b 的大作中提到】
: 一样的啰嗦。
: /**
: * Definition for binary tree with next pointer.
: * public class TreeLinkNode {
: * int val;
: * TreeLinkNode left, right, next;
: * TreeLinkNode(int x) { val = x; }
: * }
: */
: public class Solution {
| l**b
发帖数: 457 | 5 hmmmm，我怎么不记得有这个条件了？
【在 j*****y 的大作中提到】
: 你这个用了 recursive感觉就不是 constant space了吧 ？
:
: 一样的啰嗦。
: /**
: * Definition for binary tree with next pointer.
: * public class TreeLinkNode {
: * int val;
: * TreeLinkNode left, right, next;
: * TreeLinkNode(int x) { val = x; }
: * }
| j*****y
发帖数: 1071 | 6 如果不是 constant space, 用 queue 就很漂亮。
题目里有 constant space 的要求
【在 l**b 的大作中提到】
: hmmmm，我怎么不记得有这个条件了？
| l*****a
发帖数: 14598 | 7 dummy node, 先link root
然后每次以当前list为基础，得到下一层的list...
【在 j*****y 的大作中提到】
: leetcode 上的这道题谁有简洁一些的代码阿？ 自己的写的有点惨不忍睹
| j*****y
发帖数: 1071 | 8 做了前面 20道题 :)
【在 p*****2 的大作中提到】
: 大牛POJ做的咋样了？
| j*****y
发帖数: 1071 | 9 不错。 thanks. 简单多了.
/**
* 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) {
TreeLinkNode dummyCur(0), dummyNext(0);
TreeLinkNode *cur = &dummyCur, *p = &dummyNext;
dummyCur.next = root;
while(cur->next)
{
while(cur->next)
{
if(cur->next->left)
{
p->next = cur->next->left;
p = p->next;
}
if(cur->next->right)
{
p->next = cur->next->right;
p = p->next;
}
cur = cur->next;
}
dummyCur.next = dummyNext.next;
cur = &dummyCur;
p = &dummyNext;
dummyNext.next = NULL;
}
}
};
【在 l*****a 的大作中提到】
: dummy node, 先link root
: 然后每次以当前list为基础，得到下一层的list...
|
|
