Tag:leetcode
Article From:https://www.cnblogs.com/liuliu5151/p/9124367.html

Given a binary tree

```struct TreeLinkNode {
}```

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`.

Note:

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

Example:

Given the following binary tree,

```     1
/  \
2    3
/ \    \
4   5    7```

After calling your function, the tree should look like:

```     1 -> NULL
/  \
2 -> 3 -> NULL
/ \    \
4-> 5 -> 7 -> NULL```

The meaning of the question is:

Given an arbitrary two binary tree, each node has next pointer.

Try to point the next pointer to the adjacent node on the right side of the same layer.

Ideas:

Recursion, the solution is very clever.

`Using 1 as curr, connect curr.left:2 and curr.right:3 with pre. Because the next of root node 1 points to null and leaves the for loop.`
```　　　　　　　　 　　 1  ( curr )--->null
/  \
dummy(-1):pre--> 2---> 3
/ \    \
4   5    7Connect (dummy.next) is called recursively because dummy.next points.2，here2 For curr. Use pre to connect curr.left:4 and curr.right:5.```
```　　　　　　　　 　　        1
/        \
2（curr）---> 3
/ \            \dummy(-1):pre--> 4--->5           7```
`Continue with the for cycle, curr = curr.next, when curr is 3. Continue using pre to connect curr.left (3 left child tree to Null) and curr.right:7.`
`　　 　　              1  `
```　　　　　　　　 　   /    \
2 ---> 3(curr)　　　　　　　　     / \     \dummy(-1):pre--> 4--->5 --->7```
`Because at this point, curr's next points to null and exits the for loop.`
`Continue to invoke connect (dummy.next) recursively until root = = null, return`

Code：

``` 1 public class Solution {
2     public void connect(TreeLinkNode root) {
3         if (root == null) return;
4
6         for (TreeLinkNode curr = root, prev = dummy;
7                 curr != null; curr = curr.next) {
8             if (curr.left != null){
9                 prev.next = curr.left;
10                 prev = prev.next;
11             }
12             if (curr.right != null){
13                 prev.next = curr.right;
14                 prev = prev.next;
15             }
16         }
17         connect(dummy.next);
18     }
19 }```