Binary Tree Level Order Traversa

Binary Tree Level Order Traversal.png

解題思路 ：

兩種做法:

1. BSF: 用 queue 實現
2. DFS: 加上一個 counter 來紀錄每次要儲存的值在第幾層 這個做法需要一開始就先知道 vector 的 size 才能直接用 counder 當 index 來儲存 所以要先拿到 tree 的高度

C++ code :

<pre><code>
//BFS solution

class Solution {

/**
 * @param root: The root of binary tree.
 * @return: Level order a list of lists of integer
 */

public:

vector<vector<int>> levelOrder(TreeNode *root) {
    // write your code here
    vector<vector<int>> v;
    if(root == nullptr) return v;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
        vector<int> level;
        int cont = q.size();
        for(int i = 0; i < cont; i++)
        {
            TreeNode *tmp = q.front();
            level.emplace_back(tmp->val);
            q.pop();
            if(tmp->left) q.push(tmp->left);
            if(tmp->right) q.push(tmp->right);
        }
        v.emplace_back(level);
    }
    return v;
}

};

//DSF solution
class Solution {

/**
 * @param root: The root of binary tree.
 * @return: Level order a list of lists of integer
 */

public:

int getHeight(TreeNode *root)
{
    if(!root) return 0;
    return 1 + max(getHeight(root->left), getHeight(root->right));
}

void DFS(TreeNode *root, vector<vector<int>> &v, int n)
{
    if(root){
        v[n].emplace_back(root->val);
        n++;
        DFS(root->left, v, n);
        DFS(root->right, v, n);
    }
    
}

vector<vector<int>> levelOrder(TreeNode *root) {
    // write your code here
    vector<vector<int>> res(getHeight(root));
    DFS(root, res, 0);
    return res;
}

};