在Populating Next Right Pointers in Each Node問題的基礎(chǔ)上，難度20，方法一樣。都是類似Binary Tree Level Order Traverse，都是把樹看成一個無向圖，然后用BFS的方式，需要記錄每一層的ParentNumInQueue以及ChildNumInQueue, 初始值為1和0，以后每次ParentNumInQ減至0說明這一層已經(jīng)遍歷完畢，這一層的Child數(shù)將成為下一層的ParentNumInQ

 1 /** 2  * Definition for binary tree with next pointer. 3  * public class TreeLinkNode { 4  *     int val; 5  *     TreeLinkNode left, right, next; 6  *     TreeLinkNode(int x) { val = x; } 7  * } 8  */ 9 public class Solution {10     public void connect(TreeLinkNode root) {11         if (root == null) return;12         LinkedList<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();13         queue.add(root);14         int ParentNumInQ = 1;15         int ChildNumInQ = 0;16         TreeLinkNode pre = null;17         while (!queue.isEmpty()) {18             TreeLinkNode cur = queue.poll();19             ParentNumInQ--;20             if (pre == null) {21                 pre = cur;22             }23             else {24                 pre.next = cur;25                 pre = pre.next;26             }27             if (cur.left != null) {28                 queue.add(cur.left);29                 ChildNumInQ++;30             }31             if (cur.right != null) {32                 queue.add(cur.right);33                 ChildNumInQ++;34             }35             if (ParentNumInQ == 0) {36                 ParentNumInQ = ChildNumInQ;37                 ChildNumInQ = 0;38                 pre.next = null;39                 pre = null;40             }41         }42     }43 }