116.給定一個(gè) 完美二叉樹(shù) ，其所有葉子節(jié)點(diǎn)都在同一層，每個(gè)父節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)。二叉樹(shù)定義如下：

二叉樹(shù)定義

填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL。
初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。

示例

● 進(jìn)階：
你只能使用常量級(jí)額外空間。

使用遞歸解題也符合要求，本題中遞歸程序占用的?？臻g不算做額外的空間復(fù)雜度。

解題思路：前序遍歷

按照題意，最先想到的就是層次遍歷。
但是題目要求常量級(jí)空間，而層次遍歷需要借助一個(gè)隊(duì)列。那我們要怎么做呢？來(lái)分析一下。

假設(shè)目前有一個(gè)節(jié)點(diǎn)node（e.g 圖中的2），我們很容易獲得左右孩子節(jié)點(diǎn)：node.left（e.g 4）、node.right(e.g 5)
因此，對(duì)于【左孩子→右孩子】(e.g 4→5)來(lái)說(shuō)我們可以很容易辦到，但關(guān)鍵是右孩子如何處理呢？
——觀察不難得知，如果此時(shí)node.next（e.g 3）如果存在，且已經(jīng)連接好了（e.g 2→3），那么我們完全可以借助node找到右孩子連接的那個(gè)節(jié)點(diǎn)（e.g 2→3，3的左孩子為6，實(shí)現(xiàn)5→6）（即通過(guò)上層連接下層）

● 由于處理下一層的時(shí)候，上一層必須處理好，所以我們可以通過(guò)先序遍歷。
可以用迭代法，或者遞歸法。但迭代法需要借助棧，因此本題只能用遞歸法了。

? 注意：遞歸的單層邏輯是 處理當(dāng)前節(jié)點(diǎn)node的左右孩子連接！
(1) 如果當(dāng)前節(jié)點(diǎn)node == null 或者 node.left == null && node.right == null，說(shuō)明無(wú)需連接。
(2) 因?yàn)槭菨M二叉樹(shù)，因此，不滿足上述情況，一定同時(shí)存在左右孩子。
(3) 因?yàn)槭菨M二叉樹(shù)，如果node.next不存在，說(shuō)明node.right.next一定為null。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if(root == null || root.left == null || root.right == null) return root;
        root.left.next = root.right;
        if(root.next != null) root.right.next = root.next.left;
        connect(root.left);
        connect(root.right);
        return root;
    }
}

117.給定一個(gè)二叉樹(shù) 。二叉樹(shù)定義如下：

二叉樹(shù)定義

填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL 。初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL 。

示例

● 進(jìn)階：
你只能使用常量級(jí)額外空間。

使用遞歸解題也符合要求，本題中遞歸程序占用的?？臻g不算做額外的空間復(fù)雜度。

由116題可知，在設(shè)置next的時(shí)候，要利用上層的節(jié)點(diǎn)來(lái)做。我們通過(guò)父節(jié)點(diǎn)來(lái)給孩子節(jié)點(diǎn)的next賦值！?
——因此一個(gè)很重要的點(diǎn)在于！【需要保證上一層的節(jié)點(diǎn)的next已經(jīng)被設(shè)置好了，那么才能進(jìn)行這一層的設(shè)置】?

● 分析：
其實(shí)這道題如果用隊(duì)列來(lái)做非常好做。但是這里咱們追求常量級(jí)空間，因此不使用BFS。
——那么可以使用遞歸去做嗎？答案是不行！因?yàn)?strong>即使是前序遍歷，也不能保證上一層的next被設(shè)置好！

舉例

● 解題思路：模擬 + 設(shè)置三指針
定義三個(gè)指針：
(a) cur：表示當(dāng)層訪問(wèn)的節(jié)點(diǎn)【初始化為root，表示第一層的起始節(jié)點(diǎn)】
(b) preChild：表示前一個(gè)next需要被連接的孩子(下層)節(jié)點(diǎn)【初始化為null】（用于連接）
(c) nextCur：表示下一層的起始節(jié)點(diǎn)【初始化為null】（記錄cur的下一個(gè)值）

● 實(shí)現(xiàn)步驟
假定cur本層及上層節(jié)點(diǎn)的next指針都已經(jīng)設(shè)置好，那么現(xiàn)要設(shè)置cur的下層節(jié)點(diǎn)的next指針：
(a) cur.left != null（如果nextCur == null，則有nextCur = cur.left，這樣可以設(shè)置下一層的起始節(jié)點(diǎn)）
說(shuō)明左孩子存在，如果preChild != null，則有：preChild.next = cur.left；此時(shí)重置 preChild = cur.left；
(b) cur.right != null（如果nextCur == null，則有nextCur = cur.right，這樣可以設(shè)置下一層的起始節(jié)點(diǎn)）
說(shuō)明有孩子存在，如果preChild != null，則有：preChild.next = cur.right；此時(shí)重置 preChild = cur.right；
(c) 將cur = cur.next，繼續(xù)從左到右尋找本層的節(jié)點(diǎn)，進(jìn)行next的連接。
當(dāng)cur == null 時(shí)，說(shuō)明下一層的next已經(jīng)設(shè)置好，如果此時(shí) nextCur != null，那么進(jìn)行下一輪的迭代！
——直到cur == null && nextCur == null，算法結(jié)束。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if(root == null) return null;
        // 基本思路：找完一層，再找一層
        Node preChild = null; // 待連接的孩子節(jié)點(diǎn)
        Node cur = root; // 當(dāng)層的某個(gè)節(jié)點(diǎn)
        Node nextCur = null; // 下一層的起始點(diǎn)
        while(cur != null || nextCur != null){
            if(cur == null){ // 這一層找完了，找下一層
                cur = nextCur;
                nextCur = null;
                preChild = null;
            }
            if(cur.left != null){
                if(nextCur == null) nextCur = cur.left; // 找到下一層的起始點(diǎn)
                if(preChild != null){
                    preChild.next = cur.left; // 將前一個(gè)點(diǎn)連接好
                }
                preChild = cur.left;
            }
            if(cur.right != null){
                if(nextCur == null) nextCur = cur.right;
                if(preChild != null){
                    preChild.next = cur.right; // 將前一個(gè)點(diǎn)連接好
                }
                preChild = cur.right;
            }
            cur = cur.next;
        }
        return root;
    }
}