116.Populating Next Right Pointers in Each Node

题目大意：对于完全二叉树的每一层，都形成一个单链表（空间复杂度是o(1)）。例子如下：

法一：层序遍历。逐层遍历，形成单链表。代码如下（耗时5ms）：

 1     public void connect(TreeLinkNode root) {
 2         if(root == null) {
 3             return;
 4         }
 5         Queue<TreeLinkNode> q = new LinkedList<TreeLinkNode>();
 6         q.offer(root);
 7         //标记当前层最后一个结点
 8         TreeLinkNode end = root;
 9         while(!q.isEmpty()) {
10             TreeLinkNode tmp = q.poll();
11             if(tmp.left != null) {
12                 q.offer(tmp.left);
13             }
14             if(tmp.right != null) {
15                 q.offer(tmp.right);
16             }
17             //如果已经到了当前层最后一个结点
18             if(tmp == end) {
19                 tmp.next = null;
20                 end = tmp.right;
21             }
22             else {
23                 tmp.next = q.peek();
24             }
25         }
26     }

View Code

另一种层序的方法，时间复杂度依旧是o(n)。代码如下（耗时5ms）：

 1     public void connect(TreeLinkNode root) {
 2         if(root == null) {
 3             return;
 4         }
 5         Queue<TreeLinkNode> q = new LinkedList<TreeLinkNode>();
 6         q.offer(root);
 7         while(!q.isEmpty()) {
 8             //当前层一共有多少结点数
 9             int len = q.size();
10             //遍历当前层的所有结点
11             for(int i = 0; i < len; i++) {
12                 TreeLinkNode tmp = q.poll();
13                 //注意只计算到当前层倒数第二个结点即可。因为如果计算到最后一个的话，q中有值，会导致next出错。
14                 if(i < len - 1) {
15                     tmp.next = q.peek();
16                 }
17                 if(tmp.left != null) {
18                     q.offer(tmp.left);
19                 }
20                 if(tmp.right != null) {
21                     q.offer(tmp.right);
22                 }
23             }
24         }
25     }

View Code

法二（借鉴）：先序遍历。优点模拟的思想，左孩子的next一定指向右孩子，因为是完全二叉树；右孩子的next的情况要看当前结点有没有右兄弟即next是否为空，如果next不为空，则右孩子指向当前结点右兄弟的左孩子，如果next为空，则右孩子next为null。代码如下（耗时0ms）：

 1     public void connect(TreeLinkNode root) {
 2         if(root == null) {
 3             return;
 4         }
 5         //由于是完全二叉树，所以如果存在左结点，一定存在右结点
 6         if(root.left != null) {
 7             root.left.next = root.right;
 8         }
 9         if(root.right != null) {
10             //如果当前结点有右兄弟，则其右孩子的next指向其右兄弟的左孩子
11             if(root.next != null) {
12                 root.right.next = root.next.left;
13             }
14             //如果没有右兄弟，则说明是当前层最后一个结点
15             else {
16                 root.right.next = null;
17             }
18         }
19         connect(root.left);
20         connect(root.right);
21     }

View Code

法三（借鉴）：两层for循环。逐层遍历，里层for循环表示遍历当前层。符合题目，空间复杂度o(1)。代码如下（耗时0ms）：

 1     public void connect(TreeLinkNode root) {
 2         if(root == null) {
 3             return;
 4         }
 5         TreeLinkNode pre = root, cur = null;
 6         //外层循环是遍历到二叉树的第几层
 7         while(pre.left != null) {
 8             cur = pre;
 9             //里层循环是针对每一层，将其下面一层形成单链表
10             while(cur != null) {
11                 //左孩子的next一定是右孩子
12                 cur.left.next = cur.right;
13                 //右孩子的next要么是null要么是当前结点右兄弟的左孩子
14                 if(cur.next != null) {
15                     cur.right.next = cur.next.left;
16                 }
17                 //遍历当前结点的右兄弟
18                 cur = cur.next;
19             }
20             pre = pre.left;
21         }
22     }

View Code