## Question

>[Leetcode.102 Binary Tree Level Order Traversal
](https://leetcode.com/problems/binary-tree-level-order-traversal/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

var levelOrder = function(root) {
    if(!root) return [];
    const q = [root];
    const ans = [];
    while(q.length){
        const row = [];
        const len = q.length;
        for(let i = 0; i < len; i++){
            const curr = q.shift();
            row.push(curr.val);
            if (curr.left) q.push(curr.left)
            if (curr.right) q.push(curr.right)
        }
        ans.push(row);
    }
    return ans;
};

:::

<hr/>

### Sol

:::spoiler Code

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return [];
    const queue = [root]
    const result = [];
    while(queue.length){
        const length = queue.length;
        const subArr = [];
        for(let i = 0; i < length; i++) {
             let curr = queue.shift();
             if(!curr) return 
             subArr.push(curr.val)
             if(curr.left) queue.push(curr.left)
             if(curr.right) queue.push(curr.right)
             
        }
        result.push(subArr);
    }
    return result;
};

:::

<hr/>

### 東
A twist of typical BFS, remembering current level count before adding more nodes into the queue

:::spoiler Code

// Time O(n) | Space O(n) - n is the number of nodes

var levelOrder = function(root) {
    if(!root) {
        return [];
    }
    let queue = [root];
    const result = [];
    
    while(queue.length !== 0) {
        const levelNodeCount = queue.length;
        const currLevelValues = [];
        
        for(let i = 0; i < levelNodeCount; i++) {
            const currNode = queue.shift();
            currLevelValues.push(currNode.val);

            if(currNode.left) {
                queue.push(currNode.left);
            }

            if(currNode.right) {
                queue.push(currNode.right);
            }
        }

        result.push(currLevelValues);
    }
    return result;
};

:::

<hr/>

### Jessie

:::spoiler Code

var levelOrder = function (root) {

  const result = [];
  const queue = [];
  let level = 0;

  if (!root) return result;

  // 待處理的放進 queue 並備註 level
  queue.push({ node: root, level });

  //  當 queue 還有東西要處理時，持續處理到沒東西需要處理為止 result 就會出來了
  while (queue.length > 0) {

    const { node, level } = queue.pop();

    //  result 的 level index 放一個新 array 進去
    if (!result[level]) result[level] = [];

    //  依照 level 存入 result
    result[level].push(node.val);

    // 待處理的放進 queue 並備註 level
    if (node.right) queue.push({ node: node.right, level: level + 1 });
    if (node.left) queue.push({ node: node.left, level: level + 1 });
  }

  return result;
};

:::

<hr/>

### 皮皮

:::spoiler Code

:::

<hr/>

### Howard

:::spoiler Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # solution 1: BFS with level recorded
        # time O(N)
        # space O(N)
        from collections import deque
        result = []
        q = deque()
        q.append((root, 0))
        
        while q:
            n, l = q.popleft()
            if not n:
                continue
            if len(result) == l:
                result.append([n.val])
            else:
                result[l].append(n.val)
            q.append((n.left, l+1))
            q.append((n.right, l+1))
        
        return result
    
    def levelOrder2(self, root: Optional[TreeNode]) -> List[List[int]]:
        # solution 2: BFS with 2 queues
        # time O(N)
        # space O(N)
        from collections import deque
        result = []
        temp = deque()  # 用來記錄整層資料
        q = deque()    # 用來做 BFS 的資料結構
        if root:
            temp.append(root)
        
        while temp:
            # 開始 BFS 之前先把整層存進結果
            result.append([x.val for x in temp])
            q = temp
            temp = deque()
            
            while q:
                n = q.popleft()
                if n.left:
                    temp.append(n.left)
                if n.right:
                    temp.append(n.right)
        
        return result

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::