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:
- 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
思路:一般层次遍历需要申请队列,但是有了next指针,我们只需记录每层最左的节点,所以可以做到use constant extra space
class Solution {
public:
void connect (TreeLinkNode *root){
TreeLinkNode* parent;
TreeLinkNode* current;
TreeLinkNode* nextParent = root;
while(nextParent){ //new level started
parent = nextParent;
nextParent = parent->left;
current = nextParent;
if(!current) return; //add next pointer
current->next = parent->right;
current = current->next;
if(!current) return;
while(parent->next){
parent = parent->next;
current->next = parent->left;
current = current->next;
if(!current) return;
current->next = parent->right;
current = current->next;
if(!current) return;
}
}
}
};