填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針

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

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL。

初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。

示例 1：

輸入：root = [1,2,3,4,5,6,7]
輸出：[1,#,2,3,#,4,5,6,7,#]
解釋：給定二叉樹如圖 A 所示，你的函數(shù)應(yīng)該填充它的每個(gè) next 指針，以指向其下一個(gè)右側(cè)節(jié)點(diǎn)，如圖 B 所示。序列化的輸出按層序遍歷排列，同一層節(jié)點(diǎn)由 next 指針連接，'#' 標(biāo)志著每一層的結(jié)束。

方法一：層次遍歷

public Node connect(Node root) {
    if (root == null) {
        return root;
    }
    Node res = root;
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            root = queue.poll();
            if (i < size - 1) {
                root.next = queue.peek();
            }
            if (root.left != null) {
                queue.offer(root.left);
            }
            if (root.right != null) {
                queue.offer(root.right);
            }
        }
    }
    return res;
}

方法二：使用已建立的next指針
第一種 是這兩個(gè)串聯(lián)的節(jié)點(diǎn)都有一個(gè)共同的父節(jié)點(diǎn)，通過父節(jié)點(diǎn)就可以將這兩個(gè)子節(jié)點(diǎn)串聯(lián)起來

第二種 是這兩個(gè)串聯(lián)的節(jié)點(diǎn)的父節(jié)點(diǎn)不同，對于這種情況，如果我們能將這一層的上一層串聯(lián)好。那么可以通過父節(jié)點(diǎn)的next找到鄰居，完成串聯(lián)。

也就是說當(dāng)我們要串聯(lián)第 i 層節(jié)點(diǎn)時(shí)，需要先完成第 i-1 層的節(jié)點(diǎn)串聯(lián)
第一層最多只有一個(gè)節(jié)點(diǎn)，不需要串聯(lián)
第二層最多只有兩個(gè)節(jié)點(diǎn)，借助根節(jié)點(diǎn)就可以完成串聯(lián)了
第三層串聯(lián)時(shí)，上一層已經(jīng)串聯(lián)完了，所以第三層可以完成串聯(lián)
同理，可以完成第四層，第五層，第N層的串聯(lián)

public Node connect(Node root) {
    if (root == null) {
        return root;
    }
    Node head = root;
    while (head.left != null) {
        Node p = head;
        while (p != null) {
            p.left.next = p.right;
            if (p.next != null) {
                p.right.next = p.next.left;
            }
            p = p.next;
        }
        head = head.left;    
    }
    return root;
}

方法三：遞歸

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

填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針 II

給定一個(gè)二叉樹：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

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

示例 1

輸入：root = [1,2,3,4,5,null,7]
輸出：[1,#,2,3,#,4,5,7,#]
解釋：給定二叉樹如圖 A 所示，你的函數(shù)應(yīng)該填充它的每個(gè) next 指針，以指向其下一個(gè)右側(cè)節(jié)點(diǎn)，如圖 B 所示。序列化輸出按層序遍歷順序（由 next 指針連接），'#' 表示每層的末尾。

使用已建立的 next 指針

• 從第一層開始（第一層只有一個(gè) root 節(jié)點(diǎn)），每次循環(huán)遍歷當(dāng)前層的鏈表節(jié)點(diǎn)，通過節(jié)點(diǎn)的 left 和 right 得到下一層的節(jié)點(diǎn)。
• 把下一層的節(jié)點(diǎn)從左到右連接成一個(gè)鏈表。
• 拿到下一層鏈表的頭節(jié)點(diǎn)，進(jìn)入下一輪循環(huán)。

代碼實(shí)現(xiàn)時(shí)，可以用一個(gè)哨兵節(jié)點(diǎn)來表示「第一個(gè)節(jié)點(diǎn)之前的節(jié)點(diǎn)」，從而減少一些關(guān)于空節(jié)點(diǎn)的判斷邏輯。

public Node connect(Node root) {
    if (root == null) {
        return root;
    }
    Node dummy = new Node();
    Node p = root;
    while (p != null) {
        Node q = dummy;
        while (p != null) {
            if (p.left != null) {
                q.next = p.left;
                q = q.next;
            }
            if (p.right != null) {
                q.next = p.right;
                q = q.next;
            }
            p = p.next;
        }
        p = dummy.next;
        dummy.next = null;
    }
    return root;
}

遞歸
DFS 這棵樹，從根節(jié)點(diǎn) 1 出發(fā)，向左遞歸到 2，再向左遞歸到 4。
這三個(gè)節(jié)點(diǎn)正好是每一層的第一個(gè)節(jié)點(diǎn)（類似鏈表頭），用一個(gè)數(shù)組 pre 記錄，即 pre[0] 為節(jié)點(diǎn) 1，pre[1] 為節(jié)點(diǎn) 2，pre[2] 為節(jié)點(diǎn) 4。pre的下標(biāo)就是節(jié)點(diǎn)的深度。
繼續(xù)遞歸到 5（深度為 2），從 pre[2] 中拿到節(jié)點(diǎn) 4，把 4 的 next 指向 5。然后更新 pre[2] 為節(jié)點(diǎn) 5，這樣在后面遞歸到節(jié)點(diǎn) 7 時(shí)，就可以從 pre[2] 中拿到節(jié)點(diǎn) 5，把 5 的 next 指向 7 了。

private List<Node> pre = new ArrayList<>();

public Node connect(Node root) {
    dfs(root, 0);
    return root;
}

private void dfs(Node root, int level) {
    if (root == null) {
        return;
    }
    if (level == pre.size()) {
        pre.add(root);
    } else {
        pre.get(level).next = root;
        pre.set(level, root);
    }
    dfs(root.left, level + 1);
    dfs(root.right, level + 1);
}