[C++] LeetCode : Binary Tree Zigzag Level Order Traversal

Question

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

 

이진트리의 root 가 주어졌을 때 지그재그로 노드의 값을 출력하는 함수를 작성하라.

 

제약사항

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

---

Solution

문제를 풀 때 고려한 사항

• 빈 트리 구조일 때도 정상 동작해야 한다. 

---

Solution

stack 두개를 사용해서 해결한다. zigzag이기 때문에 넣는 순서를 왼쪽 자식 트리부터 or 오른쪽 자식 트리부터를 번갈아 가며 진행해준다. 

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans; 
        if(root == NULL) return ans;

        stack<TreeNode*> curr_level;
        stack<TreeNode*> next_level;

        curr_level.push(root);

        bool left_to_right = true;
        vector<int> data;
        while(!curr_level.empty()){
            TreeNode * top = curr_level.top();
            data.push_back(top->val);
            curr_level.pop();

            if(left_to_right){
                if(top->left){
                    next_level.push(top->left);
                }
                if(top->right){
                    next_level.push(top->right);
                }
            }else{
                if(top->right){
                    next_level.push(top->right);
                }
                if(top->left){
                    next_level.push(top->left);
                }
            }

            if(curr_level.empty()){
                left_to_right = !left_to_right;
                swap(curr_level, next_level);
                ans.push_back(data);
                data.clear();
            }
        }

        return ans;
    }
};

• Time complexity : O(N) 
• Space Complexity : O(N) 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/108/trees-and-graphs/787/

Explore - LeetCode