[Leetcode] 102. Binary Tree Level Order Traversal

Identifying the Problem

이진트리의 레벨별로의 값들을 묶어 2차원 벡터로 리턴한다.

 

 

Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]

Organizing thoughts

이진 트리의 탐색 깊이가 깊어질 때,

2차원 벡터의 size를 하나 씩 늘리며,

해당 깊이에 해당하는 값을 2차원 벡터에 추가한다.

Sourcecode

class Solution {
    
public:
    vector<vector<int>> ans; //정답 벡터
    int max_depth = 0; 
    //resize가 줄어들게 되면, 기존 값들이 다 없어지기에, 최대 size를 유지해준다.
    
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        if(!root) return ans; //빈 트리면 null 리턴
        
        ans.push_back(vector<int>()); //행 추가
	    ans[0].push_back(root->val); //root 값 추가
        
        insert(root->left,1); //재귀로 깊이 탐색
        insert(root->right,1);
        
        return ans;
    }
    void insert(TreeNode* root, int c)
    {
        if(!root) return;
        
        else
        {
            max_depth = c > max_depth? c : max_depth; //깊이가 늘어나면 최대 깊이 수정
            ans.resize(max_depth+1); //최대 깊이에 맞게 size 수정한다.
            ans[c].push_back(root->val); //레벨에 맞는 곳에 값 추가
            
            insert(root->left,c+1);
            insert(root->right,c+1);
        }
    }
};

 

New things learned

• c++ resize를 사용시 size가 5였다가 3으로 다시 준다면, size가 5였을 때 값은 다 날라간다.

c++ vector reserve vs resize : 미리 공간을 만들어 놓고 쓰면 안 될까요?