# 【LeetCode】102. Binary Tree Level Order Traversal

## Question link
[Link](https://leetcode.com/problems/binary-tree-level-order-traversal/description/)
## Intuition
> 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).
(給定一個二元樹的根，返回層序走訪過程中經過節點的數值，順序為左至右)

經典的樹走訪問題，此題目共二種解法
1. Recursive
2. Queue(FIFO) 先訪問先處理

## Approach

### Recursive
使用遞迴方式逐層往下訪問節點，並用Pre order(NLR)的順序向下訪問
1. 遇到 `NULL` 節點就直接返回
2. 如果當前深度等於結果向量的大小，則創建並添加一個新的空向量來表示該層
3. 將當前節點的值添加到對應深度的向量中
4. 遞迴處理左子樹，將深度加1
5. 遞迴處理右子樹，將深度加1

### Queue
使用Queue的FIFO特性來處理元素，Queue裡元素為該層的所有元素，由於每一次push到Queue都會是被訪問節點的左或右子樹，但是
1. 批次處理Queue裡面所有的元素，直到該層全部處理完畢
2. 批次處理完後將儲存的結果放到回傳向量中，並開始下層的訪問

## Complexity

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

## Code

### Solution 1 Recursive

class Solution {
public:
    void solve(vector<vector<int>>& ans, TreeNode* root, int depth){
        if (!root) return;
        if (ans.size() == depth) {
            ans.push_back(vector<int>());
        }
        ans[depth].push_back(root->val);
        solve(ans, root->left, depth + 1);
        solve(ans, root->right, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        solve(ans, root, 0);
        return ans;
    }
};

### Solution 2 Queue

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int size = q.size();
            vector<int>l(size, 0);
            for (int i = 0; i < size; i++) {
                TreeNode* front = q.front();
                q.pop();
                l[i] = front->val;
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
            ans.push_back(l);
        }
        return ans;
    }
};