// https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

var height = function(root) {
    if(!root) return 0;
    return Math.max(height(root.left), height(root.right)) + 1;
}
var dfs = function(root, index, res) {
    if(!root) return;
    if(index == 0) res.push(root.val);
    dfs(root.left, index-1, res);
    dfs(root.right, index-1, res);
}
var zigzagLevelOrder = function(root) {
    let h = height(root);
    let ans = [];
    for(let i=0; i<h; i++) {
        let level = [];
        dfs(root, i, level);
        ans.push(level);
    }
    for(let i=0; i<ans.length; i++) {
        if(i % 2 != 0) {
            ans[i].reverse();
        }
    }
    return ans;
};