[Leet code - 102] Binary Tree Level Order Traversal ✅

Binary Tree Level Order Traversal - LeetCode

문제

Input : 정수형 값을 가진 이진 트리

Output : 트리의 레벨별로 묶어 vector로 반환

 

 

시간 복잡도

※1초에 1억번을 대략적인 기준으로 삼는다.

 

n이 $0 \le n \le 2000$이므로 $O(n^2)$부터 고려해볼 수 있다.

 

 

해결 과정

대놓고 BFS를 사용하라고 만든 문제이기 때문에 BFS를 사용한다.

BFS는 모든 원소를 한 번씩 탐색하기 때문에 O(n)과 같으므로 충분히 사용가능하다.

 

 

구현

using pti = pair<TreeNode*,int>;

vector<vector<int>> levelOrder(TreeNode* root) {
        
        vector<vector<int>> result;
        result.reserve(2001);

        if (root == nullptr) return result;

        // first : TreeNode | second : level
        queue<pti> q;
        q.push(pti(root, 0));

        while(q.empty() == false)
        {
            // queue pop
            TreeNode* now = q.front().first;
            int nowLev = q.front().second;
            q.pop();

            // work
            // 현재 인덱스가 유효하지 않은지 확인
            while(result.size() < nowLev + 1) result.push_back(vector<int>());

            // insert result
            result[nowLev].push_back(now->val);

            // queue push
            if (now->left != nullptr) q.push(pti(now->left, nowLev + 1));
            if (now->right != nullptr) q.push(pti(now->right, nowLev + 1));
        }

        return result;
    }

 

 

되돌아보기

n == 0일때 확인하는 걸 깜빡해서 좀 시간을 소요했다

입력 값 잘 보기!

 

 

개선 코드

나는 각 원소마다 level을 첨부하여  level을 확인했는데, 따로 첨부하지 않고 level단위로 처리를 하는 쉬운 방법도 존재했다.

vector<vector<int>> levelOrder(TreeNode* root) 
{
    vector<vector<int>> result;
    result.reserve(2001);
   
    if(root == nullptr) return result;

    queue<TreeNode*> q;
    q.push(root);

    while(q.empty() == false)
    {
    	int levSize = q.size();
        result.push_back(vector<int>());
        for (int i = 0; i < levSize; ++i)
        {
            TreeNode* now = q.front();
            q.pop();
            result.back().push_back(now->val);

            if (now->left != nullptr) q.push(now->left);
            if (now->right != nullptr) q.push(now->right);
        }
    }

    return result;
}

안그래도 항상 BFS에서 level단위로 작업하는 문제가 있을 때 귀찮았는데 좋은 거 하나 알아갑니다~~