Two-stacks JavaScript solution
We can easily solve this problem using two stacks. The first stack s1 is used to traverse the current level of the tree, and the second stack s2 is used to trac
We can easily solve this problem using two stacks. The first stack `s1` is used to traverse the current level of the tree, and the second stack `s2` is used to track the nodes in the next level. Also, we need to have a `flag` to indicate the traversal direction has been flipped when the current level has been traversed completely.\n```\n/**\n * @param {TreeNode} root\n * @return {number[][]}\n */\nvar zigzagLevelOrder = function(root) {\n    if (!root) return []; // Sanity check\n    \n    var result = [], level = [], s1 = [root], s2 = [], flag = true;\n    \n    while (s1.length > 0) {\n        var node = s1.pop(), left = node.left, right = node.right;\n\n        // Handle the current node\n        level.push(node.val);\n\n        // Get ready for the next level\n        // the key of zigzag traversal is to control the order of pushing\n        // left and right sub children\n        if (flag) {\n            if (left)  s2.push(left);\n            if (right) s2.push(right);\n        } else {\n            if (right) s2.push(right);\n            if (left)  s2.push(left);\n        }\n        \n        // We just finish traversing the current level\n        if (s1.length === 0) {\n            result.push(level);\n            level = [];\n            flag = !flag;\n            // Continue to traverse the next level\n            s1 = s2;\n            s2 = [];\n        }\n    }\n    \n    return result;\n};\n```\n\nTime complexity: `O(n)`\nSpace complexity: The max width of the tree
[]