[LeetCode] 2415. Reverse Odd Levels of Binary Tree

https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/

leetcode - Reverse Odd Levels of Binary Tree

문제 유형: 이진트리, bfs

문제 난이도: Medium

 

문제

Given the root of a perfect binary tree, reverse the node values at each odd level of the tree.

• For example, suppose the node values at level 3 are [2,1,3,4,7,11,29,18], then it should become [18,29,11,7,4,3,1,2].

Return the root of the reversed tree.

A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.

The level of a node is the number of edges along the path between it and the root node.

 

포화이진트리의 루트가 주어집니다. 홀수레벨의 노드들의 값들을 뒤집으시오.

 

풀이

bfs를 통해서 트리를 순회하는데, 현재 레벨이 짝수인 경우는 수를 뒤집는 작업을 한 번 거쳐줘야 한다.

스택을 만들어서 값들을 쌓고, 꺼내면서 자식들의 키를 새로 할당해주면 뒤집어진다.

홀수 레벨의 경우는 평범하게 순회한다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

/**
 * 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:
    TreeNode* reverseOddLevels(TreeNode* root) {
        int level = 0;

        queue<TreeNode*> q;
        q.push(root);
        stack<int> keyStack;

        while(!q.empty()) {
            int qsize = q.size();
            if(level%2 == 0) {
                for(int i = 0; i < qsize; ++i) {
                    auto curr = q.front();
                    if(!curr || !(curr -> left)) return root;
                    q.pop();
                    keyStack.push(curr -> left -> val);
                    keyStack.push(curr -> right -> val);

                    q.push(curr);
                }
                for(int i = 0; i < qsize; ++i) {
                    auto curr = q.front();
                    if(!curr) return root;
                    q.pop();
                    
                    int newKey = keyStack.top();
                    keyStack.pop();
                    curr -> left -> val = newKey;
                    q.push(curr -> left);
                    
                    newKey = keyStack.top();
                    keyStack.pop();
                    curr -> right -> val = newKey;
                    q.push(curr -> right);
                }
            } else {
                for(int i = 0; i < qsize; ++i) {
                    auto curr = q.front();
                    if(!curr) return root;
                    q.pop();
                    q.push(curr -> left);
                    q.push(curr -> right);
                }
            }
            level++;
        }

        return root;
    }
};