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 to NULL
.
Initially, all next pointers are set to NULL
.
Note:
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
讲真这道题目废了我挺久时间的,是自己没考虑全面吧,写一波直接提交总是wa
c++
class Solution {
public:
void connect(TreeLinkNode *root) {
if(root==NULL) return;
queue<TreeLinkNode*> q;
TreeLinkNode* pre = NULL;
q.push(root);
int i=0;int lever=0; int y = 0;
while(!q.empty())
{
TreeLinkNode* temp = q.front();
q.pop();
if(i==0||((i-y)==pow(2.0,lever)))
{
if(pre!=NULL)
pre->next = temp;
temp->next = NULL;
y = i;
lever++;
}
else{
if(i==y+1) {pre = temp; pre->next =NULL;}
else { pre->next = temp;pre = temp;pre->next=NULL;
}
}
i++;
if(temp->left!=NULL) q.push(temp->left);
if(temp->right!=NULL) q.push(temp->right);
}
}
};