題目描述:
給定一個二叉樹,傳回其按層次周遊的節點值。 (即逐層地,從左到右通路所有節點)。
例如:
給定二叉樹: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
傳回其層次周遊結果:
[
[3],
[9,20],
[15,7]
]
算法思想:采用DFS周遊整棵樹,如果目前節點所在層(從0層開始)是一個新層,即len(res)==level(利用下标從0開始)。舉例:當周遊到第0層時,是一個新層,此時res中沒有vector,說明需要添加一個新的vector,則需要添加一個新的vector,否則,就找到對應層的vector,向裡面添加元素。
/**
* 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>> res;
void travel(TreeNode* root,int level){
if(res.size()==level){
vector<int> temp;//res.push_back(vector<int>());匿名寫法
res.push_back(temp);
}
res[level].push_back(root->val);
if(root->left)
travel(root->left,level+1);
if(root->right)
travel(root->right,level+1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
if(root==NULL)
return res;
travel(root,0);
return 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;
queue<TreeNode*> q;
if(root==NULL)
return res;
q.push(root);
q.push(NULL);//NULL用于分隔不同的層
vector<int> cur;
while(!q.empty()){
TreeNode *temp=q.front();
q.pop();
if(temp==NULL){//得到NULL說明目前層已經周遊完成,并且目前層所有的子節點已經加入到隊列中了
res.push_back(cur);//将已經得到的結果,加入到res中
cur.resize(0);//重置cur
if(q.size()>0)//如果隊列中還有元素,添加NULL用于不同層之間的分隔
q.push(NULL);
}else{
cur.push_back(temp->val);
if(temp->left)q.push(temp->left);
if(temp->right)q.push(temp->right);
}
}
return 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*> que;
que.push(root);
while(!que.empty()){//每次判斷隊列是否為空時,都是一個新層,每一個新層都建立一個vector
int size=que.size();
vector<int> temp;
while(size--){
TreeNode* top=que.front();
que.pop();
temp.push_back(top->val);
if(top->left)
que.push(top->left);
if(top->right)
que.push(top->right);
}
res.push_back(temp);
}
return res;
}
};