摘要：原題鏈接廣度優(yōu)先搜索復雜度時間空間思路相當于是遍歷二叉樹。代碼記錄本層節(jié)點的個數(shù)最后一個節(jié)點的是，不做處理遞歸法復雜度時間空間遞歸棧空間思路由于父節(jié)點多了指針，我們不用記錄父節(jié)點的父節(jié)點就能直到它相鄰的節(jié)點。

Given a binary tree
struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

Populate each next pointer to point to its next right node. If there
is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
For example, Given the following perfect binary tree,
     1
   /  
  2    3
 /   / 
4  5  6  7

After calling your function, the tree should look like:
     1 -> NULL
   /  
  2 -> 3 -> NULL
 /   / 
4->5->6->7 -> NULL

Note:
You may only use constant extra space. You may assume that it is a
perfect binary tree (ie, all leaves are at the same level, and every
parent has two children).

原題鏈接

時間 O(N) 空間 O(N)

相當于是Level Order遍歷二叉樹。通過一個Queue來控制每層的遍歷，注意處理該層最后一個節(jié)點的特殊情況。此方法同樣可解第二題。

public class Solution {
    public void connect(TreeLinkNode root) {
        Queue q = new LinkedList();
        if(root!=null) q.offer(root);
        while(!q.isEmpty()){
            //記錄本層節(jié)點的個數(shù)
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeLinkNode curr = q.poll();
                //最后一個節(jié)點的next是null，不做處理
                if(i < size - 1){
                    TreeLinkNode next = q.peek();
                    curr.next = next;
                }
                if(curr.left != null) q.offer(curr.left);
                if(curr.right != null) q.offer(curr.right);
            }
        }
    }
}

時間 O(N) 空間 O(N) 遞歸棧空間

由于父節(jié)點多了next指針，我們不用記錄父節(jié)點的父節(jié)點就能直到它相鄰的節(jié)點。對于左子節(jié)點來說，其next節(jié)點就是父節(jié)點的右節(jié)點。對于右子節(jié)點來說i，其next節(jié)點就是父節(jié)點的next節(jié)點的左子節(jié)點。以此遞歸。

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null) return;
        //左子節(jié)點的next是右子節(jié)點
        if(root.left != null) root.left.next = root.right;
        if(root.right != null){
        //右子節(jié)點的next是父節(jié)點的next的左子節(jié)點
            root.right.next = root.next == null? null:root.next.left;
        }
        connect(root.left);
        connect(root.right);
    }
}

時間 O(N) 空間 O(1)

上述兩種方法都會使用額外空間。實際上，我們可以用一個指針記錄當前層內(nèi)遍歷到的節(jié)點，另一個指針記錄下一層第一個節(jié)點，來省去空間開銷。這樣，我們可以基于上一層的next指針進行橫向遍歷，同時遍歷到該層盡頭時又能使用記錄下的下一層第一個節(jié)點的指針來直接跳轉(zhuǎn)到下一層。

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null) return;
        //記錄該層當前節(jié)點的指針，也叫做父節(jié)點，我們通過遍歷父節(jié)點，來連接它們的子節(jié)點
        TreeLinkNode p = root;
        //記錄下層第一個節(jié)點的指針
        TreeLinkNode first = null;
        while(p != null){
            //當first為空時，說明剛跳轉(zhuǎn)到新的一層，需要設置下一層的第一個節(jié)點了
            if(first == null){
                first = p.left;
            }
            //如果有左子節(jié)點，則其next是右子節(jié)點，如果沒有，則遍歷結(jié)束
            //因為我們實際上是將下一層的節(jié)點用next指針連接，所以當遍歷到葉子結(jié)點時已經(jīng)沒有下一層
            if(p.left != null){
                p.left.next = p.right; 
            } else {
                break;
            }
            //如果父節(jié)點有next，則next的左子節(jié)點是父節(jié)點的右子節(jié)點的next，如果沒有，說明這層遍歷完了，轉(zhuǎn)入下一層
            if(p.next != null){
                p.right.next = p.next.left;
                p = p.next;
            } else {
                p = first;
                first = null;
            }
        }
    }
}

時間 O(N) 空間 O(1)

因為我們確定的知道每個非葉子節(jié)點都有左右節(jié)點，所以我們可以一層一層鏈接。只要根據(jù)當前層的next指針形成的鏈表，將下一層的左右左右連起來就行了。

public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode head = root;
        while(head != null){
            // 記錄當層第一個節(jié)點
            TreeLinkNode tmpHead = head;
            // 開始鏈接下一層
            while(head != null){
                //鏈接左節(jié)點
                if(head.left != null) head.left.next = head.right;
                //鏈接右節(jié)點
                if(head.right != null) head.right.next = head.next != null ? head.next.left : null;
                head = head.next;
            }
            // 跳到下一層第一個節(jié)點
            head = tmpHead.left;
        }
    }
}

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

原題鏈接

時間 O(N) 空間 O(N) 遞歸棧空間

由于父節(jié)點多了next指針，我們不用記錄父節(jié)點的父節(jié)點就能直到它相鄰的節(jié)點。對于左子節(jié)點來說，其next節(jié)點就是父節(jié)點的右節(jié)點。對于右子節(jié)點來說i，其next節(jié)點就是父節(jié)點的next節(jié)點的左子節(jié)點。以此遞歸。

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null) return;
        if(root.left != null) root.left.next = root.right;
        if(root.right != null){
            root.right.next = root.next == null? null:root.next.left;
        }
        connect(root.left);
        connect(root.right);
    }
}

時間 O(N) 空間 O(1)

當不是完全二叉樹時，左子節(jié)點或者右子節(jié)點都有可能為空，每個葉子節(jié)點的深度也不一定相同，所以退出循環(huán)的條件、每層頭節(jié)點的確定方法以及next指針的賦值都要改變。首先，next指針不再是分左右子節(jié)點來直接賦值，而是對記錄下來的上個節(jié)點的next賦當前操作的節(jié)點。其次，退出循環(huán)不能再像上一題一樣到最后一層就可以退出，因為當前節(jié)點會不斷更新，只有當前節(jié)點為空時才能退出。最后頭節(jié)點可能是左子節(jié)點，也可能是右子節(jié)點。

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null) return;
        TreeLinkNode p = root;
        TreeLinkNode first = null;
        //上一個節(jié)點，我們給上一個節(jié)點的next賦值，然后再更新上一個節(jié)點為它的next
        TreeLinkNode last = null;
        while(p != null){
            //下一層的頭節(jié)點有可能是左子節(jié)點也有可能是右子節(jié)點
            if(first == null){
                if(p.left != null){
                    first = p.left;
                } else if(p.right != null){
                    first = p.right;
                }
            }
            //更新last和last的next
            if(p.left != null){
                if(last != null){
                    last.next = p.left;
                }
                last = p.left;
            }
            if(p.right != null){
                if(last != null){
                    last.next = p.right;
                }
                last = p.right;
            }
            //如果當前節(jié)點沒有next，則該層結(jié)束，轉(zhuǎn)入下一層，否則就繼續(xù)
            if(p.next != null){
                p = p.next;
            } else {
                p = first;
                first = null;
                last = null;
            }
            
        }
    }
}

時間 O(N) 空間 O(1)

第一問層次遞進的延伸。上一問中我們不需要一個額外的指針來控制我們一層中鏈接的節(jié)點，因為我們知道肯定是左右左右的順序，而這題中左右節(jié)點可能不存在，所有我們要用一個指針記錄這一層中我們鏈接到了哪個節(jié)點，方便我們鏈接下一個節(jié)點。

public class Solution {
    public void connect(TreeLinkNode root) {
        // head是上一層的節(jié)點，我們用上一層節(jié)點的next形成鏈表，來鏈接當前這層
        TreeLinkNode head = root;
        while(head != null){
            // 記錄鏈接到哪個節(jié)點的額外指針
            TreeLinkNode curr = new TreeLinkNode(0);
            // tmp指向該層的第一節(jié)點
            TreeLinkNode tmp = curr;
            while(head != null){
                // 嘗試鏈接左節(jié)點
                if(head.left != null){
                    curr.next = head.left;
                    curr = curr.next;
                }
                // 嘗試鏈接右節(jié)點
                if(head.right != null){
                    curr.next = head.right;
                    curr = curr.next;
                }
                head = head.next;
            }
            // 將head移動到當前這層的的第一個，準備鏈接下一層
            head = tmp.next;
        }
    }
}