[LeetCode] 102. Binary Tree Level Order Traversal

LeetCode - 102. Binary Tree Level Order Traversal 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/binary-tree-level-order-traversal/

풀이

이진 트리를 레벨 순회(tree level order traversal)했을 때 각 노드가 갖는 값을 반환하는 문제이다. 레벨 순회를 하려면 동일한 레벨에 있는 노드에 접근해야 하므로 깊이를 우선하는 DFS로는 풀 수 없고, 너비를 우선하는 BFS를 활용하여 풀 수 있다.

• 각 노드의 위치가 nullptr 값인지 확인하면서 현재 노드 기준에서 left와 right를 순서대로 큐에 넣어준다.

소스 코드

/**
 * 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<int>> ans;
        if (root == nullptr) {
            return ans;
        }
        queue<TreeNode*> q;
        q.push(root);
        ans.resize(1);
        ans[0].push_back(root->val);
        while (!q.empty()) {
            int sz = (int)q.size();
            int ansIdx = (int)ans.size();
            ans.push_back(vector<int>());
            for(int s = 0; s < sz; ++s) {
                TreeNode *now = q.front();
                q.pop();
                if (now->left != nullptr) {
                    q.push(now->left);
                    ans[ansIdx].push_back(now->left->val);
                }
                if (now->right != nullptr) {
                    q.push(now->right);
                    ans[ansIdx].push_back(now->right->val);
                }
            }
        }
        ans.pop_back();
        return ans;
    }
};