102.BinaryTreeLevelOrderTraversal.md

102. Binary Tree Level Order Traversal

Medium

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        
        vector<vector<TreeNode *>> levels;

        vector<TreeNode *> parent_vector;
        vector<TreeNode *> children_vector;
        if(root)parent_vector.push_back(root);
        
        while(parent_vector.size()>0){
            levels.push_back(parent_vector);
            children_vector.clear();
            while(parent_vector.size()>0){
                if(parent_vector[0]->left) children_vector.push_back(parent_vector[0]->left);
                if(parent_vector[0]->right) children_vector.push_back(parent_vector[0]->right);
                parent_vector.erase(parent_vector.begin());
            }
            parent_vector = children_vector;
        }
        vector<vector<int>> levels_vals;
        for(int i = 0; i<levels.size(); i++){
            vector<int> current_level_vals;
            for(int j = 0; j<levels[i].size(); j++){
                current_level_vals.push_back(levels[i][j]->val);
            }
            levels_vals.push_back(current_level_vals);
        }
        return levels_vals;
    }
};