[OJ.leetcode] binary-tree-level-order-traversal

https://oj.leetcode.com/problems/binary-tree-level-order-traversal/

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

 

 /*

 solution

 1. BFS + 매 iteration마다 marker를 queue에 삽입하여 level  구분하기

 2. counter를 이용하여 매 iteration마다 자식노드 갯수 세기

 3. in-order로 depth level을 알수있으므로 바로 push(loop로 구현할 경우  in-place로 구현 가능)

 */

 

class Solution {

    public:

    vector<vector<int>> levelOrder(TreeNode *root) {

        vector<vector<int>> res;

        if(root == NULL) return res;

        

        vector<int> level;

        queue<TreeNode*> input;

        int cnt = 1;

        input.push(root);

      

        while(!input.empty()) {

            level.clear();

            int levelCnt = 0;

            

            for(int i=0 ; i<cnt; i++) {

                TreeNode* node = input.front();

                level.push_back(node->val);

                input.pop();

                

                if(node->left != NULL) {

                    input.push(node->left);

                    levelCnt++;

                }

                

                if(node->right != NULL) {

                    input.push(node->right);

                    levelCnt++;

                }

            }

            

            cnt = levelCnt;

            res.push_back(level);

        }

    }

};