[leetCode] 103. Binary Tree Zigzag Level Order Traversal

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

Binary Tree Zigzag Level Order Traversal - LeetCode

 

해당 문제는 지그재그로 이동하면서 노드를 검사하는 문제이다.

 

/**
 * 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:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

        vector<vector<int>> result;
        Search(root, 0, result);
        for (int i = 1; i < result.size(); i += 2) {
            reverse(result[i].begin(), result[i].end());
        }
        return result;
    }

    void Search(TreeNode* node, int depth, vector<vector<int>>& result) {
        if (node == nullptr) return;

        if (result.size() == depth) {
            result.push_back(vector<int>());
        }
        result[depth].push_back(node->val);

        Search(node->left, depth + 1, result);
        Search(node->right, depth + 1, result);
    }
};

첫 번째로 먼저 모든 노드를 vector에 다 담고, 홀 수번째 노드들만 뒤집는 것이다. 이러면 완벽한 지그재그 트리가 되긴한다.

 

근데 이 로직은 별로 효율적이진 못하다. 재귀 + reverse 함수로 연산 비용이 상당히 나가게 된다.

BFS방식대로 코드를 다시 짜보면 아래와 같다.

/**
 * 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:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

        vector<vector<int>> result;
        if (!root) 
         return result;

        queue<TreeNode*> q;
        q.push(root);
        bool flip = true;

        while(!q.empty())
        {
            int levelSize = q.size();
            vector<int> currVec(levelSize);

            for(int i=0; i<levelSize; i++)
            {
                TreeNode* node = q.front(); q.pop();

                int index = flip ? i : (levelSize -1 -i) ;

                currVec[index] = node->val;

                if (node->left != nullptr)
                    q.push(node->left);
                if (node->right != nullptr)
                    q.push(node->right);
            }
            result.push_back(currVec);
            flip = !flip;
        }

        return result;
    }
};

 처음 root를 넣고, 그 다음 아래 자식 노드를 검사할 때 지그재그 방향이니까, 뒤집는 방향으로 담아야 한다. 

그래서 flip bool 타입을 두고, 이 점을 활용해서 배열내 요소들을 재구성해 주면 된다.