Skip to content

Instantly share code, notes, and snippets.

  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save lyleaf/d71b71ec7a35f5b81a486895cdc48c60 to your computer and use it in GitHub Desktop.
/**
我的方法用了一个queue,再用一个NULL指针来分辨是不是一层的。
看了答案以后发现optimized的解法是,不需要用queue,因为这个next的link已经可以serve as queue.
* 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) {
queue<TreeLinkNode*> q;
q.push(root);
q.push(NULL);
while (q.front()){
while(q.front()){
TreeLinkNode* cur = q.front();
q.pop();
cur->next = q.front();
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
q.pop();
q.push(NULL);
}
}
};
@lyleaf
Copy link
Author

lyleaf commented Aug 23, 2016

我得只用这个linked list再做一遍。思路就是linked list可以serve as queue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment