Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set toNULL
.
Initially, all next pointers are set toNULL
.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
/**
* 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) {
while(root!=NULL)
{
TreeLinkNode* next = NULL;
TreeLinkNode* pre = NULL;
for(;root!=NULL;root=root->next) //遍歷的原因是root是一個鏈表
{
if(next==NULL)
next = (root->left != NULL) ? root->left : root->right;
if(root->left)
{
if(pre)
pre->next = root->left;
pre = root->left;
}
if(root->right)
{
if(pre)
pre->next = root->right;
pre = root->right;
}
}
root = next;
}
}
};
