LeetCode 117. Populating Next Right Pointers in Each Node II 填充每个节点的下一个右侧节点指针II（Java）

题目：

Given a binary tree

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.

Follow up:

• You may only use constant extra space. Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Input: root = [1,2,3,4,5,null,7] Output: [1,#,2,3,#,4,5,7,#] Explanation: Given the above 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.

Constraints:

• The number of nodes in the given tree is less than 6000. -100 <= node.val <= 100

解答：

本题与 LeetCode 116 题的区别在于，不是一个满二叉树，而是任意一个二叉树。依然采用层级遍历的方法 不使用额外空间的话，采用下列指针遍历的方式，其中注意，我们需要用 level 指针记录下一层中的第一个节点。

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

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    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) {
          
   
        //node 用来表示遍历当前层的节点
        Node node = root;
        while(node != null) {
          
   
            //level用来存储下一层的第一个节点，采用虚拟指针的方式
            Node level = new Node(0);
            level.next = null;
            //cur表示遍历到的下一层节点
            Node cur = level;
            while(node != null) {
          
   
                if(node.left != null) {
          
   
                    cur.next = node.left;
                    cur = cur.next;
                }
                if(node.right != null) {
          
   
                    cur.next = node.right;
                    cur = cur.next;
                }
                node = node.next;
            }
            node = level.next;
        }
        return root;
    }
}

如果使用额外的恒定空间，也可以采用队列的方式。其中需要判断是否当前出队列的节点，是否为本层的最后一个节点。实现如下：

class Solution {
          
   
    public Node connect(Node root) {
          
   
        if(root == null) {
          
   
            return root;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
          
   
            int size = queue.size();
            for(int i=0; i<size; i++) {
          
   
                Node node = queue.poll();
                //若不是本层最后一个节点
                if(i != size-1) {
          
   
                    node.next = queue.peek();
                }
                if(node.left != null) {
          
   
                    queue.add(node.left);
                }
                if(node.right != null) {
          
   
                    queue.add(node.right);
                }                
            }
        }
        return root;
    }