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,
代码语言：javascript复制 1
/
2 3
/
4 5 7After calling your function, the tree should look like:
代码语言：javascript复制 1 -> NULL
/
2 -> 3 -> NULL
/
4-> 5 -> 7 -> NULL题意和116一样，只不过这里的树不保证每一个节点都有左右孩子。
找next的时候一定要找到有孩子的next才行，而且为了避免next的next没有连接的情况，应该先遍历右子树。
代码语言：javascript复制/**
* 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) {
if(!root) return ;
if(root->right)
{
TreeLinkNode *p=root;
while(p->next)
{
p=p->next;
if(p->left)
{
root->right->next=p->left;
break;
}
else if(p->right)
{
root->right->next=p->right;
break;
}
}connect(root->right); //先遍历右子树
}
if(root->left)
{
if(root->right)
root->left->next=root->right;
else
{
TreeLinkNode *p=root;
while(p->next)
{
p=p->next;
if(p->left)
{
root->left->next=p->left;
break;
}
else if(p->right)
{
root->left->next=p->right;
break;
}
}
}
connect(root->left);
}
}
};
