Eric 的小站

1
输入：root = [1,2,3,4,5,null,7]
2
输出：[1,#,2,3,#,4,5,7,#]
3
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

1
输入：root = []
2
输出：[]

1
class Solution {
2
    vector<Node*> pre;
3
public:
4
    Node* connect(Node* root) {
5
        dfs(root,0);
6
        return root;
7
    }
8

9
    void dfs(Node* node, int depth) {
10
        if(node == nullptr){
11
            return ;
12
        }
13
        if(depth == pre.size()){
14
            pre.push_back(node);
15
        }else{
16
            pre[depth]->next = node;
17
            pre[depth] = node;
18
        }
19
        dfs(node->left,depth+1);
20
        dfs(node->right,depth+1);
21
    }
22
};

1
class Solution {
2
public:
3
    Node* connect(Node* root) {
4
        if (root == nullptr)
5
            return nullptr;
6
        vector<Node*> q = {root};
7
        while(!q.empty()){
8
            vector<Node*> nxt;
9
            for (int i = 0; i < q.size(); i++) {
10
                Node* node = q[i];
11
                if (i) {
12
                    q[i - 1]->next = node;
13
                }
14
                if (node->left) {
15
                    nxt.push_back(node->left);
16
                }
17
                if (node->right) {
18
                    nxt.push_back(node->right);
19
                }
20
            }
21
            q = move(nxt);
22
        }
23
        return root;
24
    }
25
};