題目描述:
給定一個二叉樹,傳回其按層次周遊的節點值。 (即逐層地,從左到右通路所有節點)。
例如:
給定二叉樹:
[3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
傳回其層次周遊結果:
[
[3],
[9,20],
[15,7]
]
AC C++ Solution:
遞歸:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
buildvector(root,0);
return res;
}
void buildvector(TreeNode *root, int depth)
{
if(root == NULL) return;
if(res.size() == depth)
res.push_back(vector<int>());
res[depth].push_back(root->val);
buildvector(root->left, depth+1);
buildvector(root->right,depth+1);
}
private:
vector< vector<int> > res;
};
隊列:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int> > res;
if(!root) return res;
queue<TreeNode*> q;
q.push(root);
q.push(NULL);
vector<int> cur_vec;
while(!q.empty()) {
TreeNode *t = q.front();
q.pop();
if(t == NULL) {
res.push_back(cur_vec);
cur_vec.resize(0);
if(q.size() > 0)
q.push(NULL); //每層之間用一個NULL作為分隔符
}
else { //把每個節點的值存入cur_vec,并把下一層的節點加入隊列
cur_vec.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
}
return res;
}
};