leetcode题解-429-N叉树的层序遍历

发表于 | 分类于

题目

My way

递归实现BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
private:
    void helper(vector<vector<int>>& vvi, int level, Node* root)
    {
        if (!root)  return ;

        // add new vector<int> for saving new level elements
        if (vvi.size() == level)
        {
            vvi.push_back(vector<int>());
        }

        vvi[level].push_back(root->val);
        for (auto it : root->children)
        {
            helper(vvi, level+1, it);
        }

    }
public:
    vector<vector<int>> levelOrder(Node* root) 
    {
        vector<vector<int>> vvi;
        helper(vvi, 0, root);

        return vvi;   
    }
};

手动队列BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        if (!root)  return vector<vector<int>>();

        vector<vector<int>> vvi;
        deque<Node*> q;
        q.push_back(root);

        while(!q.empty())
        {
            vector<int> vi;

            int size = q.size();
            for (int i = 0; i < size; ++i)
            {
                auto front = q.front();
                q.pop_front();

                vi.push_back(front->val);
                
                for (auto& it : front->children)
                {
                    if (it) q.push_back(it);
                }
            }

            vvi.push_back(vi);
        }

        return vvi;
    }
};