Binary Tree Zigzag Level Order Traversal Problem


Description

LeetCode Problem 103.

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == NULL)
            return ans;
        
        queue<TreeNode*> bfsQ;
        bfsQ.push(root);
        int len = 1, cnt = 1;
        vector<int> line;
        TreeNode* curr;
        while (!bfsQ.empty()) {
            len = bfsQ.size();
            line.clear();
            for (int i = 0; i < len; i ++) {
                curr = bfsQ.front();
                bfsQ.pop();
                if (curr != NULL) {
                    line.push_back(curr->val);
                    bfsQ.push(curr->left);
                    bfsQ.push(curr->right);
                } 
            }
            if (cnt % 2 == 0)
                reverse(line.begin(), line.end());
            cnt ++;
            if (!line.empty())
                ans.push_back(line);
        }
        return ans;
    }
};




Related Posts

Word Ladder Problem

LeetCode 127. Given two words, beginWord and endWord, and a...

Word Ladder II Problem

LeetCode 126. Given two words, beginWord and endWord, and a...

Surrounded Regions Problem

LeetCode 130. Given an m x n matrix board containing...

Binary Tree Zigzag Level Order Traversal Problem

LeetCode 103. Given the root of a binary tree, return...

Binary Tree Level Order Traversal Problem

LeetCode 102. Given the root of a binary tree, return...

Binary Tree Level Order Traversal II Problem

LeetCode 107. Given the root of a binary tree, return...