Tree: Populating Next Right Pointers in Each Node II *

public class Solution { public void connect(TreeLinkNode root) { if(root == null) return; ArrayList<TreeLinkNode> list = new ArrayList<TreeLinkNode>(); list.add(root); while(!list.isEmpty()){ ArrayList<TreeLinkNode> current = list; list = new ArrayList<TreeLinkNode>(); for(int i = 0 ; i < current.size(); i++){ TreeLinkNode node = current.get(i); if(i!= current.size() -1) node.next = current.get(i+1); if(node.left!=null)list.add(node.left); if(node.right!=null) list.add(node.right); } } } }

public class Solution { public void connect(TreeLinkNode root) { if(root == null) return; TreeLinkNode p = root.next;//use p to find connection point while(p!=null){ if(p.left != null){ p = p.left; break; } if(p.right != null){ p = p.right; break; } p = p.next; } if(root.left!= null){ root.left.next = (root.right == null)?p:root.right; } if(root.right != null){ root.right.next = p; } connect(root.right); connect(root.left); } }

mistake: ？？？ why connect right first then left??

when right tree left has no child but its right child has node, the left tree will connect to null instead of right's node, so connect from right then left