Populating Next Right Pointers in Each Node
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 toNULL
.
Initially, all next pointers are set toNULL
.
Note:
You may only use constant extra space.
Recursive approach is fine, implicit stack space does not count as extra space for this problem.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
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
Solution
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) return;
Queue<TreeLinkNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
int size = queue.size();
int index = 0;
TreeLinkNode previous = null;
while (index < size) {
TreeLinkNode node = queue.poll();
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
if (previous != null) {
previous.next = node;
}
previous = node;
index++;
}
}
}
}
PreviousConstruct Binary Tree from Preorder and Inorder TraversalNextLowest Common Ancestor of a Binary Tree
Last updated
Was this helpful?