# 102. Binary Tree Level Order Traversal

### Leetcode

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

### 題目

Given the `root` of a binary tree, return *the level order traversal of its nodes' values*. (i.e., from left to right, level by level).

&#x20;

**Example 1:**

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

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

**Example 2:**

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

**Example 3:**

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

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

* **方法一**

用一個 level 屬性紀錄每個節點是在哪一層的

```
var levelOrder = function(root) {
    if(root === null) return [];
    
    const res = [];
    root.level = 0;
    const stack = [root];
    while(stack.length) {
        const node = stack.pop();
        const level = node.level;
        
        if (res[level]) {
            res[level].push(node.val);
        } else {
            res[level] = [node.val];
        }
        
        if (node.right) {
            node.right.level = level + 1;
            stack.push(node.right);
        }
        if (node.left) {
            node.left.level = level + 1;
            stack.push(node.left);
        }
    }
    
    return res;
};
```

Runtime: 101 ms, faster than 42.98% of JavaScript online submissions for Binary Tree Level Order Traversal.

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

* **方法二**

Recursion

```
var levelOrder = function(root) {
    if(root === null) return [];
    
    const res = [];
    const stack = [root];
    const helper = (node, level) => {
        if (res[level]) {
            res[level].push(node.val);
        } else {
            res[level] = [node.val];
        }
        
        if (node.left) {
            helper(node.left, level + 1);
        }
        if (node.right) {
            helper(node.right, level + 1);
        }
    }
    
    helper(root, 0)
    
    return res;
};
```

* **方法三**

Iteration

```
var levelOrder = function(root) {
    if(root === null) return [];
    
    const res = [];
    let level = 0;
    const queue = [root];
    while(queue.length) {
        res.push([]);
        const len = queue.length;
        for(let i=0; i<len; i++) {
            const node = queue.shift();
            res[level].push(node.val);
            
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
        level++;
    }
    
    return res;
};
```

Runtime: 80 ms, faster than 71.96% of JavaScript online submissions for Binary Tree Level Order Traversal.

Memory Usage: 44.9 MB, less than 5.83% of JavaScript online submissions for Binary Tree Level Order Traversal.
