Solution： Iterative 每层遍历，对应连接
思路：Because the input is a perfect binary tree that has complete nodes, the following idea for every level would work:
屏幕快照 2017-09-06 下午7.06.11.png
Time Complexity:O(N) Space Complexity: O(1)
Solution2：dfs 自round1
Time Complexity:O(N) Space Complexity: O(logN) 递归缓存
Solution Code：
public class Solution {
public void connect(TreeLinkNode root) {
TreeLinkNode level_head = root;
while (level_head != null) {
TreeLinkNode cur = level_head;
while (cur != null) {
if (cur.left != null) cur.left.next = cur.right;
if (cur.right != null && cur.next != null) cur.right.next = cur.next.left;
cur = cur.next;
}
level_head = level_head.left;
}
}
}
public class Solution {
public void connect(TreeLinkNode root) {
dfs(root);
}
private void dfs(TreeLinkNode root) {
if(root == null || root.left == null || root.right == null) return;
root.left.next = root.right;
if(root.next != null) {
root.right.next = root.next.left;
}
dfs(root.left);
dfs(root.right);
}
}
