Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
分层遍历二叉树，用BFS即可
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> Q;
vector<vector<int>> ans;
Q.push(root);
while(!Q.empty())
{
int e = Q.size(); //当前层的结束位置
vector<int> partans;
for(int i = ; i < e; i++)
{
TreeNode * p = Q.front();
Q.pop();
if(NULL != p)
{
partans.push_back(p->val);
Q.push(p->left);
Q.push(p->right);
}
}
if(!partans.empty())
ans.push_back(partans);
}
return ans;
}
};
网上DFS的代码：
class Solution {
protected:
vector<vector<int>> ans;
void dfs(TreeNode *root, int height){
if (root == NULL)
return;
while (ans.size() <= height)
ans.push_back(vector<int>());
ans[height].push_back(root->val);
dfs(root->left, height + );
dfs(root->right, height + );
}
public:
vector<vector<int>> levelOrder(TreeNode* root) {
dfs(root, );
return ans;
}
};
Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
跟上面只是顺序变了，加个reverse就行了。