LeetCode/102-BinaryTreeLevelOrderTraversal.cpp at master · DionysiosB/LeetCode · GitHub

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {

private:
    std::vector<std::vector<int> > v;
    std::queue<std::pair<TreeNode *, int> > q;

public:
    std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        if(root == NULL){return v;}
        q.push(std::make_pair(root, 0));
        getVector();
        return v;
    }

    void getVector(){
        while(!q.empty()){
            std::pair<TreeNode* , int> current = q.front();
            q.pop();
            TreeNode* tn = current.first;
            int depth = current.second;

            while(depth >= v.size()){std::vector<int> u; v.push_back(u);}
            v[depth].push_back(tn->val);

            if(tn->left != NULL){q.push(std::make_pair(tn->left, depth + 1));}
            if(tn->right != NULL){q.push(std::make_pair(tn->right, depth + 1));}
        }
    }
};