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

Test Cases

Input:

(TreeNode) root = [3,9,20,null,null,15,7]

Output:

(int[]) [[3],[20,9],[15,7]]

Explanation:

Solution

        
/**
 * 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:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (root == nullptr) return {};
        bool ltr = true;
        queue<TreeNode*> q;
        vector<vector<int>> result;
        q.push(root);
        while(!q.empty()) {
            vector<int> row;
            int qs = q.size();
            while(qs > 0) {
                TreeNode *node = q.front();
                q.pop();
                if (ltr) {
                    row.push_back(node->val);
                } else {
                    row.insert(row.begin(), node->val);
                }

                if (node->left != nullptr) q.push(node->left);
                if (node->right != nullptr) q.push(node->right);
                qs--;
            }
            result.push_back(row);
            ltr = !ltr;
        }
        return result;
    }
};

    

        
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean order = true;
        int size = 1;

        while(!q.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < size; ++i) {
                TreeNode n = q.poll();
                if(order) {
                    tmp.add(n.val);
                } else {
                    tmp.add(0, n.val);
                }
                if(n.left != null) q.add(n.left);
                if(n.right != null) q.add(n.right);
            }
            res.add(tmp);
            size = q.size();
            order = order ? false : true;
        }
        return res;
    }
}

    

        
/**
 * Definition for a binary tree node.
 */
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    if (root === null) return [];
    const queue = [root];
    const res = [];
    let order = true;
    while (queue.length > 0) {
        const list = [];
        const size = queue.length;
        for(let i=0; i<size; i++) {
            const el = queue.shift();
            if (order) list.push(el.val);
            else list.unshift(el.val);
            if (el.left !== null) queue.push(el.left);
            if (el.right !== null) queue.push(el.right);
        }
        res.push(list);
        order = !order;
    }
    return res;
};

    

        
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None: return root
        q = [(root, 0)]
        mp = {}
        while len(q) > 0:
            x, h = q.pop(0)
            if h in mp:
                mp[h].append(x.val)
            else:
                mp[h] = [x.val]
            if x.left is not None: q.append((x.left, h+1))
            if x.right is not None: q.append((x.right, h+1))
        for k,v in mp.items():
            if k%2==1:
                mp[k] = mp[k][::-1]
        return mp.values()

    

Binary Tree Zigzag Level Order Traversal

Test Cases

Solution

Time Complexity: O(n)

Space Complexity: O(n)