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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!