Populating Next Right Pointers in Each Node II (Java and Python)

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

Solution : The main idea actually is tree level traversal, we can just use one node called current represent current level (start from root) and two other nodes which called nextLevelHead and nextLevelEnd to record next level's left child and right child and when current node is null then exchange current and nextLevelHead until nextLevelHead is also null

	/*
	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
	*/
	/**
	* 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;
	}
	TreeLinkNode current=root;
	TreeLinkNode nextLevelHead=null;
	TreeLinkNode nextLevelEnd=null;
	while (current!=null){
	if (current.left!=null){
	if (nextLevelHead==null){
	nextLevelHead=current.left;
	nextLevelEnd=nextLevelHead;
	}
	else{
	nextLevelEnd.next=current.left;
	nextLevelEnd=nextLevelEnd.next;
	}
	}
	if (current.right!=null){
	if (nextLevelHead==null){
	nextLevelHead=current.right;
	nextLevelEnd=nextLevelHead;
	}
	else{
	nextLevelEnd.next=current.right;
	nextLevelEnd=nextLevelEnd.next;
	}
	}
	current=current.next;
	if (current==null){
	current=nextLevelHead;
	nextLevelHead=null;
	nextLevelEnd=null;
	}
	}
	}
	}

view raw PopulatingNextRightPointersInEachNodeII.java hosted with ❤ by GitHub

	"""
	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
	"""
	# Definition for a binary tree node
	# class TreeNode:
	# def __init__(self, x):
	# self.val = x
	# self.left = None
	# self.right = None
	# self.next = None
	class Solution:
	# @param root, a tree node
	# @return nothing
	def connect(self, root):
	if not root:
	return
	current=root
	nextLevelHead=None
	nextLevelEnd=None
	while (current):
	if (current.left):
	if nextLevelHead:
	nextLevelEnd.next=current.left
	nextLevelEnd=nextLevelEnd.next
	else:
	nextLevelHead=current.left
	nextLevelEnd=nextLevelHead
	if (current.right):
	if nextLevelHead:
	nextLevelEnd.next=current.right
	nextLevelEnd=nextLevelEnd.next
	else:
	nextLevelHead=current.right
	nextLevelEnd=nextLevelHead
	current=current.next
	if (not current):
	current=nextLevelHead
	nextLevelHead=None
	nextLevelEnd=None

view raw PopulatingNext RightPointersInEachNodeII.py hosted with ❤ by GitHub