116. 填充每个节点的下一个右侧节点指针

116. 填充每个节点的下一个右侧节点指针

层序遍历

执行用时：3 ms, 在所有 Java 提交中击败了45.53% 的用户 内存消耗：38.9 MB, 在所有 Java 提交中击败了12.79% 的用户

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                Node poll = queue.poll();
                // 如果节点不是当前层的最后一个节点，将next指向下一个节点
                if (i > 1) {
                    poll.next = queue.peek();
                }
                if (poll.left != null) queue.add(poll.left);
                if (poll.right != null) queue.add(poll.right);
            }
        }
        return root;
    }
}

递归解法

执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户 内存消耗：38.8 MB, 在所有 Java 提交中击败了23.83% 的用户

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        if (root.left != null) {
            // left的next比较简单，直接指向root.right
            root.left.next = root.right;
            connect(root.left);
        }
        if (root.right != null) {
            // right的next指向root.next.left
            root.right.next = root.next == null ? null : root.next.left;
            connect(root.right);
        }
        return root;
    }
}