w***o
发帖数: 109 | 1 来一个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;
}
... 阅读全帖 |
|
w***o
发帖数: 109 | 2 来一个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;
}
... 阅读全帖 |
|
h****n
发帖数: 1093 | 3 不需要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 ... 阅读全帖 |
|
h****n
发帖数: 1093 | 4 不需要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 ... 阅读全帖 |
|
j********e
发帖数: 1192 | 5 我得用10多行，6行怎么写？
void addNode(Node* &head, Node* &tail, Node *node) {
if(!node) return;
if(tail)
tail = tail->next = node;
else
head = tail = node;
}
void LinkSameLayer(Node *head, Node *tail) {
if(head == NULL) return;
Node *nextHead = NULL, *nextTail == NULL;
do {
addNode(nextHead, nextTail, head->left);
addNode(nextHead, nextTail, head->right);
} while(head != tail);
LinkSameLayer(nextHead, nextTail);
}
LinkSameLayer(root, root); |
|
s***e
发帖数: 122 | 6 我觉得这个问题可能得先想清楚数据结构。我的想法是：
用一个二维的链表来存储你最后的结果(行内是单向链接，行头双向链接)：
a->b
|
c->d
节点的结构: (string s, int order, node* prevHead, node* nextHead, node* next)
用一个哈希表来存储所有的单词和对应的行头：
a->pa，b->pa，c->pc，d->pc
用一个哈希表来存储行头和对应的行尾：
pa->pb, pc->pd
这样当你加一个新的单词组的时候，我们先建一个关联列表，用来存储该单词组关联到
的所有行头。
对每个词先查哈希表看这个词是否以前出现过。如果出现过，我们就找到那个词所在
的行头，放到一个关联列表中；如果没有出现我们就把新词加到二维链表中，然后加到
哈希表中，同时把这个新行头也放到关联列表中。
当所有的单词扫描完，把关联列表排一下序，然后把二维链表中对应的行合并起来。
比如如上的时候，我们要加一个单词组e b f d：
1) 加e：哈希表中没找到，我们把它加到二维链表中
a->b
|
c->d
|
e
然后加到哈希表中
a->pa，b->pa，c |
|
