題目鏈接

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

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摆舟。

進(jìn)階：

• 你只能使用常量級(jí)額外空間亥曹。
• 使用遞歸解題也符合要求邓了，本題中遞歸程序占用的棧空間不算做額外的空間復(fù)雜度媳瞪。

示例：

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

提示：

• 樹(shù)中節(jié)點(diǎn)的數(shù)量少于 4096
• -1000 <= node.val <= 1000

解答

/*
// 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;
        Queue<Node> nodeQueue = new LinkedList<>();
        Queue<Node> parentQueue = new LinkedList<>();
        nodeQueue.add(root);
        Node node;
        while (!nodeQueue.isEmpty()) {
            // nodeQueue的出棧維護(hù)
            node = nodeQueue.poll();
            // 當(dāng)當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的右子節(jié)點(diǎn)時(shí)，填充當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)把将，
            // 且對(duì)parentQueue進(jìn)行出棧維護(hù)的操作
            if (!parentQueue.isEmpty() && parentQueue.peek().right == node) {
                if (parentQueue.peek().next != null)
                    node.next = parentQueue.peek().next.left;
                parentQueue.poll();
            }
            // 對(duì)當(dāng)前節(jié)點(diǎn)的左子結(jié)點(diǎn)填充下一節(jié)點(diǎn)的操作
            if (node.left != null) {
                node.left.next = node.right;
                // nodeQueue的入棧維護(hù)
                nodeQueue.add(node.left);
                nodeQueue.add(node.right);
            }
            // parentQueue的入棧維護(hù)
            parentQueue.add(node);
        }
        return root;*/
        // 空間復(fù)雜度優(yōu)化版
        if (root == null) return null;
        if (root.left != null) {
            root.left.next = root.right;
            // 當(dāng)前節(jié)點(diǎn)不是本層最右的節(jié)點(diǎn)時(shí)
            if (root.next != null) {
                root.right.next = root.next.left;
            }
        }
        connect(root.left);
        connect(root.right);
        return root;
    }
}