给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例：
输入：{"$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":null,"next":null,"right":{"$id":"6","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":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1}
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答：
解法1：递归：
对于这里的题目与上题是非常类似的，但是这里不是完美二叉树，所以需要考虑的更多，
对于那两步可能就不一定都有了，只有左右子节点都有才会有，如果少一个那么只需要找一个节点的next，如果左右节点都不存在，那我们根本就不需要处理这种情况，所以这样看还是讨论一下左右节点存在的情况就可以了。注意：必须先递归右节点，不然会出错，因为我们递归左节点的时候会用到右节点的。
1 /*
2 // Definition for a Node.
3 class Node {
4 public int val;
5 public Node left;
6 public Node right;
7 public Node next;
8
9 public Node() {}
10
11 public Node(int _val,Node _left,Node _right,Node _next) {
12 val = _val;
13 left = _left;
14 right = _right;
15 next = _next;
16 }
17 };
18 */
19 class Solution {
20 public Node connect(Node root) {
21 if(root==null||(root.left==null&&root.right==null))
22 return root;
23 if(root.left!=null)
24 {
25 if(root.right!=null)
26 {
27 root.left.next=root.right;
28 root.right.next=findNext(root.next);
29 }
30 else
31 {
32 root.left.next=findNext(root.next);
33 }
34 }
35 else
36 {
37 root.right.next=findNext(root.next);
38 }
39 connect(root.right);
40 connect(root.left);
41
42 return root;
43
44 }
45 public Node findNext(Node root)
46 {
47 if(root==null)
48 return null;
49 else
50 {
51 if(root.left!=null||root.right!=null)
52 {
53 if(root.left!=null)
54 return root.left;
55 else
56 return root.right;
57 }
58 else
59 return findNext(root.next);
60
61 }
62 }
63 }
解法2:迭代
还是一样的讨论左右节点存在的情况，一样的找next，注意这里递归的下一层是用last指向的第一个我们用到的存在子节点的节点，不然我们会在这一层一直找，找到null说明不存在下一层就结束了。
1 /*
2 // Definition for a Node.
3 class Node {
4 public int val;
5 public Node left;
6 public Node right;
7 public Node next;
8
9 public Node() {}
10
11 public Node(int _val,Node _left,Node _right,Node _next) {
12 val = _val;
13 left = _left;
14 right = _right;
15 next = _next;
16 }
17 };
18 */
19 class Solution {
20 public Node connect(Node root) {
21 if(root==null)
22 return root;
23 Node last=root;
24 while(last!=null)
25 {
26 while(last!=null&&last.left==null&&last.right==null)
27 last=last.next;
28 if(last==null)
29 break;
30 Node cur=last;
31 while(cur!=null)
32 {
33 if(cur.left!=null)
34 {
35 if(cur.right!=null)
36 {
37 cur.left.next=cur.right;
38 cur.right.next=findNext(cur.next);
39 }
40 else
41 cur.left.next=findNext(cur.next);
42 }
43 else if(cur.right!=null)
44 {
45 cur.right.next=findNext(cur.next);
46 }
47 cur=cur.next;
48 }
49 if(last.left!=null)
50 last=last.left;
51 else
52 last=last.right;
53 }
54 return root;
55 }
56 public Node findNext(Node root)
57 {
58 if(root==null)
59 return null;
60 if(root.left!=null)
61 return root.left;
62 else if(root.right!=null)
63 return root.right;
64 return findNext(root.next);
65
66 }
67
68 }
