🌕 117. 填充每个节点的下一个右侧节点指针 II

难度: 🌕

问题描述

---

解法 1 - 层序

/*
// 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 root;
        }
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int len = queue.size();
            Node pre = null;
            for(int i = 0; i < len; i ++) {
                Node cur = queue.poll();
                if(pre != null) {
                    pre.next = cur;
                }
                pre = cur;
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
        return root;
    }
}

---

输出 1

---

解法 2 - 迭代

/*
// 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 root;
        }
        Node topFirst = root;
        while(topFirst != null) {
            Node cur = topFirst; // 当前层首节点
            Node secondFirst = new Node(-1); // 创建下一层虚拟首节点
            Node secondCur = secondFirst;
            while(cur != null) {
                if(cur.left != null) {
                    // 下一层链表连接当前 left
                    secondCur.next = cur.left;
                    secondCur = secondCur.next;
                }
                if(cur.right != null) {
                    secondCur.next = cur.right;
                    secondCur = secondCur.next;
                }
                cur = cur.next;
            }
            // 至此，当前层的下一层节点已经全部连接完毕，跳转到下一层
            topFirst = secondFirst.next;
        }
        return root;
    }
}

---

输出 2