Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL
.
Initially, all next pointers are set to NULL
.
Note:
Example:
Given the following binary tree,
After calling your function, the tree should look like:
这道题目和上一道不同的是,它不是完全二叉树。则不能通过节点数计算是否在哪一层
c++
class Solution {
public:
void connect(TreeLinkNode *root) {
if(root==NULL) return;
queue<pair<int,TreeLinkNode*> > q;
TreeLinkNode* pre = NULL;
q.push(make_pair(1,root));
int y = 0;
while(!q.empty())
{
TreeLinkNode* temp = q.front().second;
int lever = q.front().first;
q.pop();
if(lever!=q.front().first||q.empty())
{
if(pre!=NULL)
pre->next =temp;
temp->next = NULL;
pre = NULL;
}
else{
if(lever!=y) {y=lever;pre = temp; pre->next =NULL;}
else { pre->next = temp;pre = temp;pre->next=NULL;
}
}
if(temp->left!=NULL) q.push(make_pair(lever+1,temp->left));
if(temp->right!=NULL) q.push(make_pair(lever+1,temp->right));
}
}
};