문제 링크

내 코드

그냥 DFS로도 된다. 너무 어렵게 생각하지 말자.

0ms, 77.1MB

class Solution {
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        DFS(root->left, root->right, 0);
        return root;
    }

    void DFS(TreeNode* l, TreeNode* r, int level) {
        if(!l || !r) return;

        if(!(level & 1)) {
            swap(l->val, r->val);
        }

        DFS(l->left, r->right, level + 1);
        DFS(l->right, r->left, level + 1);
    }
};

Solution

Approach 1: Depth-First Search

• 0ms, 77.08MB
• Complexity
  • Let $n$ be the number of nodes in the given tree.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(\log n)$

class Solution {
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        traverseDFS(root->left, root->right, 0);
        return root;
    }

private:
    void traverseDFS(TreeNode* leftChild, TreeNode* rightChild, int level) {
        if (leftChild == nullptr || rightChild == nullptr) {
            return;
        }
        // If the current level is odd, swap the values of the children.
        if (level % 2 == 0) {
            int temp = leftChild->val;
            leftChild->val = rightChild->val;
            rightChild->val = temp;
        }

        traverseDFS(leftChild->left, rightChild->right, level + 1);
        traverseDFS(leftChild->right, rightChild->left, level + 1);
    }
};

Approach 2: Breadth-First Search

• 3ms, 84MB
• Complexity
  • Let $n$ be the number of nodes in the given tree.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        if (!root) {
            return nullptr;  // Return null if the tree is empty.
        }

        queue<TreeNode*> q;
        q.push(root);  // Start BFS with the root node.
        int level = 0;

        while (!q.empty()) {
            int size = q.size();
            vector<TreeNode*> currentLevelNodes;

            // Process all nodes at the current level.
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                currentLevelNodes.push_back(node);

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }

            // Reverse node values if the current level is odd.
            if (level % 2 == 1) {
                int left = 0, right = currentLevelNodes.size() - 1;
                while (left < right) {
                    int temp = currentLevelNodes[left]->val;
                    currentLevelNodes[left]->val =
                        currentLevelNodes[right]->val;
                    currentLevelNodes[right]->val = temp;
                    left++;
                    right--;
                }
            }

            level++;
        }

        return root;  // Return the modified tree root.
    }
};