LeetCode : 107. Binary Tree Level Order Traversal II

처음 queue를 사용해서 문제를 풀었을 때는, 시간이 faster than 13.36%가 나와서,,,, 큰일났다 싶었다.

따라서, 다른 분들의 풀이를 참고해서 큐를 사용하지 않고 그냥 dfs로도 풀어보았다.

 

1. runtime -> faster than 13.36%, memory -> less than 62.96%

 

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        vector<vector<int>> ans;
        stack<vector<int>> st;
        
        while(!q.empty()){
            int size = q.size();
            vector<int> v;
            for(int i=0; i<size; i++){
                TreeNode* node = q.front();
                q.pop();
                
                if(node==NULL) continue;
                v.push_back(node->val);
                
                q.push(node->left);
                q.push(node->right);
            }
            
            if(v.size()==0) continue;
            st.push(v);
        }
        
        while(!st.empty()){
            ans.push_back(st.top());
            st.pop();
        }
        
        return ans;
    }
};

2. runtime -> faster than 42.85%, memory -> less than 11.01%

 

class Solution {
public:
    void Traversal(vector<vector<int>> &ans, TreeNode* node, int level){
        if(node==NULL){
            return;
        }// 새로운 level에 도달했을 때 새로운 배열을 생성해서 넣어준다.
        if(level==ans.size()){
            ans.push_back({});
        }
        
        ans[level].push_back(node->val);
        Traversal(ans, node->left, level+1);
        Traversal(ans, node->right, level+1);
    }
    
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        Traversal(ans, root, 0);
        reverse(ans.begin(), ans.end());
        
        return ans;
    }
};