Java描述 LeetCode，116. Populating Next Right Pointers in Each Node 填充一棵树的next指针

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。一起支持原创吧！纯手打有笔误还望谅解。

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 212 - 1].
-1000 <= Node.val <= 1000

Follow-up:

You may only use constant extra space.
The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注意：这里的是满二叉树 a perfect binary tree，代码不难，主要是把几种方法再回顾一下。

☘️满二叉树就好办了，首先我们可以用order level 层次遍历去做，只需要加以判断把queue里面的节点联系起来就可以了。

考虑两种情况

• 节点和next 有同一个父亲，比如4，5。
• 不是同一个父亲，比如5，6，不是同一个父亲节点，构建5的next的时候就需要通过5的父亲2的next指针找到3，再通过3.left找到6。

public Node connect(Node root) {

    if (root == null) {
        return root;
    }

    Queue queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (i < size - 1) {
                node.next = queue.peek();
            }
        }
    }
    return root;
}

time  complexity O(n)
space complexity O(n)

☘️利用先序遍历的算法，先序遍历 根左右，根一定在左孩子右孩子节点之前先访问的。借助这个，好吧，感觉其实也不一定是先序，中序也可以，其实只要根先访问到就行，因为构建next的时候，需要借助上一层的节点，根的next关系一定是要先建立好的！

public static Node connect2(Node root) {
    Stack nodeStack = new Stack<>();
    Node cur = root;
    while (cur != null || !nodeStack.isEmpty()) {
        if (cur != null) {
            if (cur.left != null) {
                cur.left.next = cur.right;
            }
            if (cur.next != null && cur.right != null) {
                cur.right.next = cur.next.left;
            }
            nodeStack.push(cur);
            cur = cur.left;
            // visit
        } else {
            cur = nodeStack.pop();
            cur = cur.right;
        }
    }
    return root;
}

public static void recursion(Node root) {
    if (root == null) {
        return;
    }
    if (root.left != null) {
        root.left.next = root.right;
    }
    if (root.next != null && root.right != null) {
        root.right.next = root.next.left;
    }
    recursion(root.left);
    recursion(root.right);
}


public static Node connect4(Node root) {
    Node cur = root;
    recursion(root);
    return root;
}

☘️在先序遍历的代码中用到了，栈来遍历所有的节点，我们刚才说过只要先遍历根就可以了，我们其实可以不用栈，只要保证从上到下去遍历所有的节点就可以了。我们可以把父亲的那一行通过next当作一个链表，通过这个父亲层的链表，我们就可以访问到全部的孩子节点，并且构建好那一层的所有next了。核心就是把父亲那一层当作一个链表用，这一点还是第一次见，可以当作一种解题思路store into my mind。

public static Node connect3(Node root) {
    if (root == null) {
        return root;
    }
    Node leftest = root;
    // 保证下一层有节点，当访问到叶子节点的时候，叶子节点的下一层是空的，
    // 这样就可以保证head.left不为空了。
    //当然也可以每次判断head.left是不是空，这样写会更好一点。当然，我是想不到的。
    while (leftest.left != null) {
        Node head = leftest;
        while (head != null) {
            head.left.next = head.right;
            if (head.next != null) {
                head.right.next = head.next.left;
            }
            head = head.next;
        }
        leftest = leftest.left;
    }
    return root;
}