Given a full binary tree, populate the nextRight pointers in each node.
In a full binary tree, each node other than the leaves has two children.
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.
Given the following perfect binary tree,
Before we passed the leftChild and rightChild to the recursion function itself, we connect the rightChild’s nextRight to the current node’s nextRight’s leftChild. In order for this to work, the current node’s nextRight pointer must be populated
The order of visits of tree node is the same as LeetCode - Binary Tree Level Order Traversal. But now we do not need to maintain a queue, since the reference next gives exactly the next node in the same level. So we can work on each level, and visit each node in a level in sequence.
Related: LeetCode - Populating Next Right Pointers in Each Node I
Read full article from LeetCode - Populating Next Right Pointers in Each Node | Darren's Blog
In a full binary tree, each node other than the leaves has two children.
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.
- 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).
X. BFS
After analysis the example, you can find two rules:
root.left.next = root.rightroot.right.next = root.next.left
Using a boolean type to check whether the
curr.left is the left most node or not- if yes, using a temporary node to track for the left node of root.
- if not, continue
After go through the two rules, we should check whether the current node is the right most node of current level. If not, we can just
curr = curr.next to continue, if yes, we should jump to the next level (Using the temporary and boolean type)2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
public void connect1(TreeLinkNode root) {
TreeLinkNode curr = root;
TreeLinkNode node = null;
boolean mostLeftNode = true;
while (curr != null) {
if (curr.left != null) {
if (mostLeftNode) {
node = curr.left; // don't need this
mostLeftNode = false;
}
curr.left.next = curr.right;
}
if (curr.right != null && curr.next != null) {
curr.right.next = curr.next.left;
}
if (null == curr.next && curr.left != null) {
curr = node; // curr = curr.left
mostLeftNode = true;
} else {
curr = curr.next;
}
}
}
|
Improvement: Instead of using a temporary node and boolean variable, we can just use one node to check for the conditions.
public void connect(TreeLinkNode root) {
TreeLinkNode n = root;
while(n != null && n.left != null) {
TreeLinkNode pre = null;
for(TreeLinkNode p = n; p != null; p = p.next) {
if(pre != null) pre.next = p.left;
p.left.next = p.right;
pre = p.right;
}
n = n.left;
}
}
http://www.programcreek.com/2014/05/leetcode-populating-next-right-pointers-in-each-node-java/public void connect(TreeLinkNode root) { if(root == null) return; TreeLinkNode lastHead = root;//prevous level's head TreeLinkNode lastCurrent = null;//previous level's pointer TreeLinkNode currentHead = null;//currnet level's head TreeLinkNode current = null;//current level's pointer while(lastHead!=null){ lastCurrent = lastHead; while(lastCurrent!=null){ if(currentHead == null){ currentHead = lastCurrent.left; current = lastCurrent.left; }else{ current.next = lastCurrent.left; current = current.next; } if(currentHead != null){ current.next = lastCurrent.right; current = current.next; } lastCurrent = lastCurrent.next; } //update last head lastHead = currentHead; currentHead = null; } }
X. BFS, but using extra queue
树的广度优先搜索题。记录下每一层的节点总个数，然后根据广度优先搜索的原则进行遍历，将非
null节点都加入到队列中，对于同一层中的节点，将其next指向队列中的下一个节点即可。 public void connect(TreeLinkNode root) {
if (root == null)
return;
LinkedList<TreeLinkNode> nodes = new LinkedList<TreeLinkNode>();
nodes.add(root);
int numOfLevelTotal = 1;
while (!nodes.isEmpty()) {
TreeLinkNode treeLinkNode = nodes.poll();
numOfLevelTotal--;
if (treeLinkNode.left != null) {
nodes.add(treeLinkNode.left);
}
if (treeLinkNode.right != null) {
nodes.add(treeLinkNode.right);
}
if (numOfLevelTotal > 0) {
treeLinkNode.next = nodes.getFirst();
} else {
numOfLevelTotal = nodes.size();
}
}
}
Use extra queue - a little different than previous one.
public void connect(TreeLinkNode root) {
if (root == null) {
return;
}
Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeLinkNode node = queue.poll();
if (i == size - 1) {
node.next = null;
} else {
node.next = queue.peek();
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
X. Recursive version:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
这题主要的难点在于处理节点5的next，因为5的next要指向它的sibling，但在5这层是没法获取到3的引用
解决方法是：由于2所在那层已经建立好next链接，所以只需由2即可得到3的引用，继而得到3的left节点
1 public void connect(TreeLinkNode root) { 4 if(root == null){ 5 return; 6 } 7 if(root.left != null){ 8 root.left.next = root.right; 9 } 10 if(root.right != null){ 11 root.right.next = (root.next != null) ? root.next.left : null; 12 } 13 14 connect(root.left); 15 connect(root.right); 16 }
public void connect(TreeLinkNode root) {
if (root == null)
return ;
if (root.left != null){
root.left.next = root.right;
}
if (root.right != null && root.next!= null)
root.right.next = root.next.left;
connect(root.left);
connect(root.right);
}
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
My first thought is to use Breadth-First Search (BFS). After all, we are connecting the nextRight node level-by-level, it is only natural to apply BFS to this problem. I mentioned this approach to the interviewer, but he was not too satisfied with it.
BFS requires memory space to store Nodes into a queue. Can we do better without extra space?
The first key to solving this problem is we have the nextRight pointer. Assume that the nextRight pointers are already populated for this level. How can we populate the next level? Easy… just populate by iterating all nodes on this level. Another key to this problem is you have to populate the next level before you go down to the next level, because once you go down, you have no parent pointer.
void connect(Node* p) {
if (p == NULL)
return;
if (p->leftChild == NULL || p->rightChild == NULL)
return;
Node* rightSibling;
Node* p1 = p;
while (p1) {
if (p1->nextRight)
rightSibling = p1->nextRight->leftChild;
else
rightSibling = NULL;
p1->leftChild->nextRight = p1->rightChild;
p1->rightChild->nextRight = rightSibling;
p1 = p1->nextRight;
}
connect(p->leftChild);
}
Added alternative solutionBefore we passed the leftChild and rightChild to the recursion function itself, we connect the rightChild’s nextRight to the current node’s nextRight’s leftChild. In order for this to work, the current node’s nextRight pointer must be populated
void connect(Node* p) {
if (!p) return;
if (p->leftChild)
p->leftChild->nextRight = p->rightChild;
if (p->rightChild)
p->rightChild->nextRight = (p->nextRight) ?
p->nextRight->leftChild :
NULL;
connect(p->leftChild);
connect(p->rightChild);
}
Iterative Version:The order of visits of tree node is the same as LeetCode - Binary Tree Level Order Traversal. But now we do not need to maintain a queue, since the reference next gives exactly the next node in the same level. So we can work on each level, and visit each node in a level in sequence.
public void connect(TreeLinkNode root) {
if (root == null) // Empty tree
return;
TreeLinkNode headOfNextLevel = root;
// Between levels
while(headOfNextLevel != null) {
// Initialize tailOfNextLevel and current, and update headOfNextLevel to null
TreeLinkNode tailOfNextLevel = null, current = headOfNextLevel;
headOfNextLevel = null;
// Within a level
while(current != null) {
// Update headOfNextLevel if we find the first node in the next level
if (headOfNextLevel == null && current.left != null)
headOfNextLevel = current.left;
// Not a leaf; link its children
if (current.left != null)
current.left.next = current.right;
// Link the currently last node in the next level to the left subtree of current node
if (tailOfNextLevel != null)
tailOfNextLevel.next = current.left;
// Update tailOfNextLevel to the right subtree, and
// move to the next node in the same level
tailOfNextLevel = current.right;
current = current.next;
}
}
}
Related: LeetCode - Populating Next Right Pointers in Each Node I
Read full article from LeetCode - Populating Next Right Pointers in Each Node | Darren's Blog
