116. Populating Next Right Pointers in Each Node
1. Description
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
struct Node {
int val;
Node *left;
Node *right;
Node *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.
2. Follow Up
- You may only use constant extra space.
- Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.
3. Example
Example 1:
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with ‘#’ signifying the end of each level.
4. Constraints
- The number of nodes in the given tree is less than 4096.
- -1000 <= node.val <= 1000
5. Solutions
My Accepted Solution
n is the number of nodes in the tree
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// Node* connect(Node* root)
Node* connect(Node *m_root)
{
if(!m_root) return nullptr;
queue<Node *> currentLevelNodes{{m_root}};
queue<Node *> nextLevelNodes;
Node *previousNode = m_root;
while(!currentLevelNodes.empty() || !nextLevelNodes.empty())
{
if(currentLevelNodes.empty())
{
swap(currentLevelNodes, nextLevelNodes);
previousNode = currentLevelNodes.front();
}
else
{
auto node = currentLevelNodes.front();
currentLevelNodes.pop();
// for the first node at every level, it will set its next pointer to itself at first
// but then, the second node will change the pointer to correct, following node
previousNode->next = node;
previousNode = node;
if(node->left) nextLevelNodes.push(node->left);
if(node->right) nextLevelNodes.push(node->right);
}
}
// but the first level node doesn't have a following node to correct it
// we have to set its next pointer to null mannually
m_root->next = nullptr;
return m_root;
}
};
5.1 Iteration(Follow Up)
n is the number of nodes in the tree
Time complexity: O(n)
Space complexity: O(1)
class Solution
{
public:
// Node* connect(Node* root)
Node* connect(Node *m_root)
{
if(!m_root) return nullptr;
auto mostLeftNode = m_root;
// the tree is a perfect binary tree, so mostLeftNode->left means whether or not we locate at the last level
while(mostLeftNode->left)
{
auto head = mostLeftNode;
while(head)
{
// link a node's left and right children
head->left->next = head->right;
// we are using current level nodes to link the next level nodes, so current level's link has been done
if(head->next) head->right->next = head->next->left;
head = head->next;
}
mostLeftNode = mostLeftNode->left;
}
return m_root;
}
};