[LeetCode] 117. Populating Next Right Pointers in Each Node II

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.

Example 1:

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

填充每个节点的下一个右侧节点指针 II。

题意跟版本一很接近，唯一不同的条件是这次给的树不一定是完美二叉树，中间会有一些节点的缺失。要求还是一样，请不要使用额外空间。

我参考了这个帖子的思路三，太巧妙了。这是一个 迭代BFS 的做法。宏观上看，你是在树的每一层从左往右遍历这棵树的所有节点。大体的思路如下，创建一个 dummy node 和一个 tail node，tail.next 是去串联当前节点的下一层上的节点。从 root 节点开始遍历，如果当前节点有左孩子和右孩子，则 tail 节点的 next 指针需要指向这些孩子节点；如果当前节点是有 next 节点的，则在处理完当前节点之后，移动到 next 节点去，tail 节点再连到 next 节点的左右孩子。直观上看，这个操作基本就是同一层的节点往右平移，同时 tail 节点从左往右连接了下一层所有的孩子节点。最后一步 cur = dummy.next，是将 cur 节点移动到下一层的最左边的节点。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public Node connect(Node root) {
 3         // corner case
 4         if (root == null) {
 5             return null;
 6         }
 7         // normal case
 8         Node cur = root;
 9         while (cur != null) {
10             // dummy是串联下一层的头部
11             // tail是串联下一层的尾部
12             Node dummy = new Node();
13             Node tail = dummy;
14             while (cur != null) {
15                 // 用tail去串联下一层的节点
16                 if (cur.left != null) {
17                     tail.next = cur.left;
18                     tail = tail.next;
19                 }
20                 if (cur.right != null) {
21                     tail.next = cur.right;
22                     tail = tail.next;
23                 }
24                 // 当前层的平移
25                 cur = cur.next;
26             }
27             // 移动到下一层，因为dummy.next实际是cur.left，或者说是tail在下一层一开始的起点
28             cur = dummy.next;
29         }
30         return root;
31     }
32 }