【LeetCode】102. Binary Tree Level Order Traversal

Question link

Link

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;
    }
};