Skip to main content

Binary Tree Zigzag Level Order Traversal

Problem​

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

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
    vector<vector<int>> ans;
    int h = -1;

   public:
    void maxHeight(TreeNode* temp, int ht) {
        if (temp == NULL) return;
        h = max(ht, h);
        maxHeight(temp->left, ht + 1);
        maxHeight(temp->right, ht + 1);
    }

    void build(TreeNode* temp, int ht) {
        if (temp == NULL) return;
        ans[ht].push_back(temp->val);
        build(temp->left, ht + 1);
        build(temp->right, ht + 1);
    }

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        TreeNode* temp;
        temp = new TreeNode;
        temp = root;
        maxHeight(temp, 0);
        ans.resize(h + 1);
        temp = root;
        build(temp, 0);
        for (int i = 1; i <= h; i += 2) {
            reverse(ans[i].begin(), ans[i].end());
        }
        return ans;
    }
};