Populating Next Right Pointers in Each Node II
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,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
解法一：
先使用队列进行BFS(O(n))，队列中的节点还需要存放当前所在层数。
如果前一个遍历到的节点pre与当前遍历到的节点cur不在同一层，那么pre->next需要指向NULL
如果在同一层，那么pre->next = cur
/**
* 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) {}
* };
*/
struct Node
{
TreeLinkNode* tree;
int level;
Node(TreeLinkNode* root, int l):tree(root),level(l) {}
}; class Solution {
public:
queue<Node*> q;
void connect(TreeLinkNode *root)
{
if(root == NULL)
return; Node* rootNode = new Node(root, );
q.push(rootNode); Node *cur = rootNode;
Node *pre = rootNode;
Node *temp = rootNode; while(!q.empty())
{
temp = q.front();
q.pop(); if(temp->tree->left)
{
Node* leftNode = new Node(temp->tree->left, temp->level+);
q.push(leftNode);
pre = cur;
cur = leftNode;
if(pre->level < cur->level)
//get to next level
pre->tree->next = NULL;
else
//still same level
pre->tree->next = cur->tree;
}
if(temp->tree->right)
{
Node* rightNode = new Node(temp->tree->right, temp->level+);
q.push(rightNode);
pre = cur;
cur = rightNode;
if(pre->level < cur->level)
//get to next level
pre->tree->next = NULL;
else
//still same level
pre->tree->next = cur->tree;
}
}
}
};
解法二：
稍作分析就可以发现，我们没有必要像BFS那样存储整个一层的节点。
只需要保留三个信息：下一层的头levelHead，本层的上一个节点prev，本层的当前节点cur即可
对于每一层来说，prev的next连接cur。当本层遍历完，通过levelHead进入下一层。
/**
* 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)
{
TreeLinkNode* cur = root; //node being visited
TreeLinkNode* levelHead = NULL; //first node in the next level
TreeLinkNode* prev = NULL; //last visited node while(cur)
{//there remains levels to be visited
while(cur)
{//there remains nodes to be visited in this level
if(cur->left)
{
if(prev)
{//cur->left is not the levelHead, link it to the prev
prev->next = cur->left;
}
else
{//cur->left is the levelHead
levelHead = cur->left;
}
prev = cur->left;
}
if(cur->right)
{
if(prev)
{//cur->right is not the levelHead, link it to the prev
prev->next = cur->right;
}
else
{//cur->right is the levelHead
levelHead = cur->right;
}
prev = cur->right;
}
cur = cur->next; //travel through this level
} cur = levelHead; //travel to the next level
levelHead = NULL;
prev = NULL;
}
}
};