116. Populating Next Right Pointers in Each Node

题目详见：116. Populating Next Right Pointers in Each Node

解法一 Level-order traversal

思路

对二叉树的每一层进行遍历，除了每一层的最后一个节点，都将 node.next 指向右边的节点。

代码

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

    public Node() {}

    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> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                Node curr = queue.poll();

                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }

                if (i != size - 1) {
                    curr.next = queue.peek();
                }
            }
        }

        return root;
    }
}

复杂度分析

• 时间复杂度 O(N) 每一个节点都进行了遍历
• 空间复杂度 O(N) 最多储存 N/2 个节点，在最后一层

解法二 预先对下一层添加节点

思路

我们对第 N 层进行 next 节点赋值时，我们要仍然要处在 N - 1 层。这样，就可以通过位于 N - 1 层的这些父节点来对 N 层的子节点进行 next 赋值操作。

我们可以在每一层的最左端设置一个指针 leftmost，遍历完成后移动到下一层；同样在每层设置一个指针，最头部开始到尾部遍历。

有两种 next 的赋值方式。当左右节点父节点相同时， node.left.next = node.right; 当左右节点父节点不同时， node.right.next = node.next.left。

当前层所有节点 next 赋值完成后，我们移动到下一层。是 leftmost = leftmost.next;

代码

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

    public Node() {}

    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 leftmost = root;

        while (leftmost.left != null) {// 到倒数第二层为止 
            Node head = leftmost;
            while (head != null) {
                // connection 1
                head.left.next = head.right;

                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                head = head.next;
            }
            leftmost = leftmost.left;
        }

        return root;
    }
}

复杂度分析

• 时间复杂度 O(N) 每一个节点都进行了遍历
• 空间复杂度 O(1) 并未使用额外空间

本作品采用《CC 协议》，转载必须注明作者和本文链接