【leetcode】Populating Next Right Pointers in Each Node II
【leetcode】Populating Next Right Pointers in Each Node II
阳光岛主
发布于 2019-02-19 11:36:04
发布于 2019-02-19 11:36:04
Question：
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
- You may only use constant extra space.
For example, Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULLAnwser 1：
/**
* 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(NULL == root){
return;
}
TreeLinkNode *cur = root->next;
TreeLinkNode *p = NULL;
while(cur != NULL){ // find last right node (left or right)
if(cur->left) {
p = cur->left;
break;
}
if(cur->right){
p = cur->right;
break;
}
cur = cur->next;
}
if(root->right){
root->right->next = p;
}
if(root->left){
root->left->next = root->right ? root->right : p;
}
connect(root->right); // from right to left
connect(root->left);
}
};注意点：
1） list为非完美二叉树，右分支可能为空，因此从right -> left 遍历
2） 从最右分支开始查找，且root没有 left 节点，则找 right 节点
Anwser 2：
/**
* 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(NULL == root){
return;
}
queue<TreeLinkNode *> Q; // save one line root(s)
queue<TreeLinkNode *> Q2; // save next one line root(s), swap with Q
Q.push(root);
while(!Q.empty()){
TreeLinkNode *tmp = Q.front();
Q.pop();
if(tmp->left) Q2.push(tmp->left);
if(tmp->right) Q2.push(tmp->right);
if(Q.empty()){
tmp->next = NULL;
queue<TreeLinkNode*> tmpQ = Q; // swap queue
Q = Q2;
Q2 = tmpQ;
} else {
tmp->next = Q.front();
}
}
}
};注意点：
1） 新增一个Q2队列，保存下一行的全部元素，辅助判断是最后一个元素（Q为空）则置为NULL
2） queue队列实现比递归要好
Anwser 3：
/**
* 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(NULL == root){
return;
}
queue<TreeLinkNode *> Q; // save one line root(s)
Q.push(root);
Q.push(NULL); // flag
while(!Q.empty()){
TreeLinkNode *tmp = Q.front();
Q.pop();
if(tmp != NULL){ // check flag
if(tmp->left) Q.push(tmp->left);
if(tmp->right) Q.push(tmp->right);
tmp->next = Q.front();
} else {
if(Q.empty()){ // pop flag = NULL, then check is empty
break;
}
Q.push(NULL);
}
}
}
};注意点：
对比第二种方法，改进点是每一行结束处，采用NULL作为标志位
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2013年04月13日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读