LeetCode——填充每个节点的下一个右侧节点指针

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

输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

思路一：层序遍历 将每一层的元素串起来。

public Node connect(Node root) {
    if (root == null) return root;
    LinkedList<Node> queue = new LinkedList<>();
    queue.add(root);
    //层序遍历
    while (!queue.isEmpty()) {
        int size = queue.size();
        //next指向一层的下一个元素
        Node curr = queue.get(0);
        for (int i = 1; i < size; i++) {
            curr.next = queue.get(i);
            curr = queue.get(i);
        }
        //更新下一层
        for (int i = 0; i < size; i++) {
            Node temp = queue.remove();
            if (temp.left != null) queue.add(temp.left);
            if (temp.right != null) queue.add(temp.right);
        }
    }
    return root;
}

时间复杂度：O(n)

空间复杂度：O(n) 不符合要求

思路二：借助next指针，进行层序遍历 依然是用next依次串连一层的元素。但是不需要借助队列，因为题目说参数是一个完美二叉树，那么我们需要用next连接两种情况的节点：

如图红色next，左孩子连接同一个父节点的右孩子，root.left.next=root.right。
如图蓝色next，右孩子连接父节点next指向的父节点的左孩子，root.right.next=root.next.left。

连接的过程依然是类似于层序遍历的结构，先连接完毕一层，再进行下一层。用一个指针p指向待连接层的前一层的最左边节点，当没有下一层的时候完成连接。

每层依然是从左向右连接，用一个指针temp指向每一层的元素，通过next进行移动，遍历一层的节点。

public Node connect(Node root) {
    if (root == null) return root;
    Node p = root;
    //p指向每一层的最左节点
    while (p.left != null) {
        Node temp = p;
        while (temp != null) {
            //第一种情况
            temp.left.next = temp.right;
            //第二种情况
            if (temp.next != null) {
                temp.right.next = temp.next.left;
            }
            temp = temp.next;
        }
        p = p.left;
    }
    return root;
}

时间复杂度：O(n)

空间复杂度：O(1)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

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

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