给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

Solution1（递归版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return NULL;
        Node* l = root->left;
        Node* r = root->right;
        while(l){
            l->next = r;
            l = l->right;
            r = r->left;
        }
        connect(root->left);
        connect(root->right);
        return root;
    }
};

Solution2（迭代版）：

一层一层的考虑，由于每个结点往后连需要用到其父节点的信息，所以我们可以在下一层结点的next指针连接完毕后，在往下一层移动时，父结点就可以利用已经连接好的next指针进行平滑的向右移动了。这样直到最后一层结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
// Definition for a Node.

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;
        Node* pre = NULL;
        Node* cur = root;
        while(cur){
            while(pre){
                pre->left->next = pre->right;
                if(pre->next){
                    pre->right->next = pre->next->left;
                }
                pre = pre->next;
            }
            pre = cur;
            cur = cur->left;
        }
        return root;
    }
};