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:
For example, Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
Anwser 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作为标志位