103. Binary Tree Zigzag Level Order Traversal

2020, Nov 08 One min read

1. Description

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).

2. Example

Example 1

Example 1
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2

Input: root = [1]
Output: [[1]]

Example 3

Input: root = []
Output: []

3. Constraints

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

4. Solutions

Breadth-first Search

n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(n)

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

        vector<vector<int>> values;
        queue<TreeNode *> nodes{{root}};
        bool left_to_right = true;
        while (!nodes.empty()) {
            const int n = nodes.size();

            vector<int> level_values(n);
            int index = left_to_right ? 0 : n - 1;
            int dir = left_to_right ? 1 : -1;

            for (int i = 0; i < n; ++i) {
                auto node = nodes.front();
                nodes.pop();
                level_values[index] = node->val;
                index += dir;

                if (node->left != nullptr) {
                    nodes.push(node->left);
                }
                if (node->right != nullptr) {
                    nodes.push(node->right);
                }
            }

            values.push_back(move(level_values));

            left_to_right = !left_to_right;
        }

        return values;
    }
};