LeetCode : 103. Binary Tree Zigzag Level Order Traversal

마찬가지로, 트리를 기반으로 한 BFS문제이다.

 

[메인 로직]

queue를 pair형태로 다음과 같이 자료구조를 짰다. => queue<pair<TreeNode*, int>> q;

second 위치에 dir변수를 두어서

dir==-1일 경우 거꾸로 저장하도록 했다.

 

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root==NULL){
            return ans;
        }
        vector<int> v;
        queue<pair<TreeNode*, int>> q;
        q.push(make_pair(root, 1));
        
        while(!q.empty()){
           int size = q.size();
            int dir;
            
            for(int i=0; i<size; i++){
                TreeNode* node = q.front().first;
                dir = q.front().second;
                
                v.push_back(node->val);
                q.pop();
                
                if(node->left!=NULL){
                    q.push(make_pair(node->left, -dir));
                }
                
                if(node->right!=NULL){
                    q.push(make_pair(node->right, -dir));
                }
            }
            
            if(dir==-1){
                vector<int> temp;
                for(int i=v.size()-1; i>=0; i--){
                    temp.push_back(v[i]);
                }
                ans.push_back(temp);                
            }else{
                ans.push_back(v);
            }
 
            v.clear();
        }
        
        return ans; 
    }
};