102

Posted on In , Views:

題目:
https://leetcode.com/problems/binary-tree-level-order-traversal/description/

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
// 經典BFS解法
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == nullptr) return ans;
        queue<TreeNode*> q;
        map<TreeNode*, int> mp;
        q.push(root);
        mp[root] = 0;
        while(!q.empty()){
            TreeNode* curr = q.front();
            q.pop();

            int level = mp[curr];
            if(ans.size() == level) ans.push_back({});
            ans.at(level).push_back(curr->val);

            if(curr->left != nullptr){
                mp[curr->left] = level+1;
                q.push(curr->left);
            }
            if(curr->right != nullptr){
                mp[curr->right] = level+1;
                q.push(curr->right);
            }
        }
        return ans;
    }
};
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
// 用陣列實作queue的優化BFS解法
#define MAXN 2005

TreeNode* q[2005];

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == nullptr) return ans;
        int l = 0, r = 0; // head and tail index, take from head, add to tail
        q[r++] = root;
        while(l < r){ // !q.empty()
            int size = r-l;
            vector<int> list;
            for(int i=0; i<size; ++i){
                TreeNode* curr = q[l++]; // q.front(), q.pop();
                list.push_back(curr->val);
                if(curr->left != nullptr){
                    q[r++] = curr->left;
                }
                if(curr->right != nullptr){
                    q[r++] = curr->right;
                }
            }
            ans.push_back(list);
        }
        return ans;
    }
};