Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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
.
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.
Example 2:
Input: root = []
Output: []
Constraints:
[0, 212 - 1]
.-1000 <= Node.val <= 1000
Follow-up:
class Solution {
public:
Node* connect(Node* root) {
if(!root) return nullptr;
queue<Node*> q;
q.push(root);
while(size(q)) {
Node* rightNode = nullptr; // set rightNode to null initially
for(int i = size(q); i; i--) { // traversing each level
auto cur = q.front(); q.pop(); // pop a node from current level and,
cur -> next = rightNode; // set its next pointer to rightNode
rightNode = cur; // update rightNode as cur for next iteration
if(cur -> right) // if a child exists
q.push(cur -> right), // IMP: push right first to do right-to-left BFS
q.push(cur -> left); // then push left
}
}
return root;
}
};
class Solution:
def connect(self, root):
if not root: return None
q = deque([root])
while q:
rightNode = None
for _ in range(len(q)):
cur = q.popleft()
cur.next, rightNode = rightNode, cur
if cur.right:
q.extend([cur.right, cur.left])
return root
class Solution {
public Node connect(Node root) {
if(root == null) return null;
Queue<Node> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()) {
Node rightNode = null;
for(int i = q.size(); i > 0; i--) {
Node cur = q.poll();
cur.next = rightNode;
rightNode = cur;
if(cur.right != null) {
q.offer(cur.right);
q.offer(cur.left);
}
}
}
return root;
}
}
In our experience, we suggest you solve this Populating Next Right Pointers in Each Node LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Populating Next Right Pointers in Each Node LeetCode Solution
I hope this Populating Next Right Pointers in Each Node LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>