Binary Tree Level Order Traversal.png
解題思路 ：
兩種做法:
- BSF: 用 queue 實現
- 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;
}
};
