103. Binary Tree Zigzag Level Order Traversal

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Binary Tree Zigzag Level Order Traversal - LeetCode

 

야근하고 왔더니 시간이 없었다..

이진트리가 주어졌을 때 지그재그로 node를 방문해 val을 2차원 벡터에 담아 반환하는 문제다.

문제 자체는 어렵지 않았는데... 촉박한 시간과 집중력 저하로 깊게 고민을 못했다.

 

처음에는 left와 right를 swap해가며 풀려고 시도했는데.. 뻘짓이였다.

현재 진행중인 level에서 아무리 swap해도 자식 노드들의 순서가 안맞기 때문이다.

이럴 때는 그냥 어디다가 동일 level의 node들을 리스트업 해두고, 순차/역순으로 그냥 뿌려주면 깔끔하게 끝난다.

 

/**
 * 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:
    void solve(TreeNode* node)
    {
        if (node == nullptr) {
            return;
        }
        
        bool left_to_right = true;
        int level = 1;
        q_.push(node);
        
        while(!q_.empty())
        {
            size_t queue_size = q_.size();
            vector<int> vec(queue_size);
            
            for (int i = 0; i < queue_size; ++i)
            {
                TreeNode* temp_node = q_.front();
                q_.pop();
                
                int index = left_to_right ? i : queue_size - 1 - i;
                vec[index] = temp_node->val;
                
                if (temp_node->left) {
                    q_.push(temp_node->left);
                }
                if (temp_node->right) {
                    q_.push(temp_node->right);
                }
            }

            left_to_right = !left_to_right;
            v_.push_back(vec);
        }
    }
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        solve(root);
        return v_;
    }
private:
    queue<TreeNode*> q_;
    vector<vector<int>> v_;
};