问题

给定一完美二叉树（叶节点在同一层且父节点都有两个子节点），与普通二叉树节点不同的是，每个节点多了一个next指针。填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

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

算法1：DFS

这道题刚开始想到的是DFS：将当前节点的左右节点指向右侧。右节点指向右侧需要当前节点的信息(cur->next->left), 因此递归函数需要传入左、右和当前节点

时间复杂度

$O(N)$

代码

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

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;
        dfs(root->left, root->right, root);
        return root;
    }

    void dfs(Node* l, Node *r, Node *root){
        if(!l && !r) return; 
        l->next = r;
        if(root->next) r->next = root->next->left;
        dfs(l->left, l->right, l);
        dfs(r->left, r->right, r);
    }
};

算法2：BFS

仔细思考，这道题的本质更像是BFS. 普通二叉树的BFS需要用到队列，因为普通二叉树当前节点的同层的右侧节点不能在当层获得；但是带有next指针的二叉树则可以，于是我们可以在当层填充子层的next指针。

时间复杂度

$O(N)$

代码

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

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;
        Node* last = root;
        while(last->left){
            for(Node* p = last; p; p = p->next){
                p->left->next = p->right;
                if(p->next) p->right->next = p->next->left;
            }
            last = last->left;
        }
        return root;
    }
};