# 103. Binary Tree Zigzag Level Order Traversal

### Leetcode

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

### 題目

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

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg)

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

**Example 2:**

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

**Example 3:**

```
Input: root = []
Output: []
```

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

BFS

記錄每層的高度，第一層高度為 1 由左至右排序，第二層高度為 2 由右至左排序 ...

```
var zigzagLevelOrder = function(root) {
    if(!root) return [];
    let queue = [root];
    
    let height = 1;
    const res = [];
    while(queue.length) {
        const isOddLevel = height % 2 === 1;
        const values = queue.map(q => q.val);
        // 如果是奇數層的話，代表要把數值從左向右加入
        // 如果是偶數層的話，代表要把數值從右向左加入
        isOddLevel ? res.push(values) : res.push(values.reverse());
        
        const len = queue.length;
        // 全部節點都由左至右順向加入
        for(let i=0; i<len; i++) {
            const node = queue.shift();
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
        height++;
    }
    
    return res;
};
```

Runtime: 91 ms, faster than 43.30% of JavaScript online submissions for Binary Tree Zigzag Level Order Traversal.

Memory Usage: 44.2 MB, less than 47.39% of JavaScript online submissions for Binary Tree Zigzag Level Order Traversal.

* **方法二**

BFS

用 `isOrderLeft` 記憶是否由左往右排

`levelList` 記錄每層的節點

`queue` 中新增 `null` 為分隔符號，代表這一層的元素排列結尾&#x20;

```
var zigzagLevelOrder = function(root) {
    if (!root) return [];
    
    const res = [];
    let levelList = [];
    
    const queue = [root, null];
    let isOrderLeft = true;
    
    while(queue.length) {
        const node = queue.shift();
        
        if (node) {
            if(isOrderLeft) {
                levelList.push(node.val);
            } else {
                levelList.unshift(node.val);
            }
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        } else {
            res.push(levelList);
            levelList = [];
            if(queue.length) {
                // add null as delimiter
                queue.push(null);
            }
            isOrderLeft = !isOrderLeft;
        }
    }
    
    return res;
};
```

Runtime: 64 ms, faster than 91.93% of JavaScript online submissions for Binary Tree Zigzag Level Order Traversal.

Memory Usage: 44.3 MB, less than 34.32% of JavaScript online submissions for Binary Tree Zigzag Level Order Traversal.

* **方法三**

DFS

用 `level` 紀錄目前節點在第幾層，並根據 `level` 的單雙判斷加入元素時是要從左邊(`push`)或右邊(`unshift`)加入

```
var zigzagLevelOrder = function(root) {
    const res = [];
    
    const dfs = (node, level) => {
        if (!node) return;
        const isLeftOrder = level % 2 === 0;
        
        if (res[level]) {
            if(isLeftOrder) {
                // 由左往右加入元素
                res[level].push(node.val);
            } else {
                // 由右往左加入元素
                res[level].unshift(node.val);
            }
        } else {
            res[level] = [node.val];
        }
        
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    
    dfs(root, 0);
    
    return res;
};
```

Runtime: 81 ms, faster than 61.48% of JavaScript online submissions for Binary Tree Zigzag Level Order Traversal.

Memory Usage: 44.4 MB, less than 13.69% of JavaScript online submissions for Binary Tree Zigzag Level Order Traversal.
