### 题目

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


### “Level Order”遍历整棵树

#### 代码

/**
* Definition for binary tree with next pointer.
*     int val;
*     TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
if (root == null) { return; }
while (!buffer.isEmpty()) {
int size = buffer.size();
for (int i = 0; i < size; i++) {
if (i+1 < size) { // 链接同层下一个元素
node.next = nextNode;
}
if (node.left != null) { buffer.add(node.left); }
if (node.right != null) { buffer.add(node.right); }
}
}
}
}


### 利用next指针按行遍历整棵树

#### 代码 （递归版）

/**
* Definition for binary tree with next pointer.
*     int val;
*     TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
recursion(root,null);
}
if (root == null) { return; }
if (nextLevel == null) {
if (root.left != null) {
nextLevel = root.left;
} else if (root.right != null) {
nextLevel = root.right;
}
}
if (root.left != null && root.right != null) { // 处理亲兄弟
root.left.next = root.right;
}
TreeLinkNode lastChild = null; // 表兄弟中的前驱左节点
if (root.right != null) {
lastChild = root.right;
} else if (root.left != null){
lastChild = root.left;
}
TreeLinkNode next = root.next, firstNextChild = null; // 表兄弟中的后续右节点
while (next != null) { // 利用next指针横向遍历
if (next.left != null) { firstNextChild = next.left; break; }
if (next.right != null) { firstNextChild = next.right; break; }
next = next.next;
}
if (lastChild != null && firstNextChild != null) {
lastChild.next = firstNextChild;
}
if (next != null) {
recursion(next,nextLevel);
} else {
recursion(nextLevel,null);
}
}
}


### 还是利用next按行遍历，简洁版

1. 如果有左子节点，前驱节点pre链接到左子节点。左子节点成为前驱点pre
2. 如果有右子节点，前驱节点pre链接到右子节点。右子节点成为前驱点pre
3. 如果左右子节点都为空，等于跳过当前节点。

#### 代码

/**
* Definition for binary tree with next pointer.
*     int val;
*     TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
TreeLinkNode cur = root; // 指向当前节点（实际处理的是当前节点的下一层子节点）
TreeLinkNode pre = null; // 前一个被链接的子节点。
while (cur != null) {
if (cur.left != null) { // 左子节点不为空
if (pre == null) {
} else {
pre.next = cur.left;
}
pre = cur.left;
}
if (cur.right != null) { // 右子节点不为空
if (pre == null) {
} else {
pre.next = cur.right;
}
pre = cur.right;
}
if (cur.next != null) {
cur = cur.next;
} else {