给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
思路
层次遍历实际上就是使用广度优先遍历(BFS)从root开始遍历。我们学数据结构的时候知道,BFS一般用队列作辅助,DFS一般用栈进行辅助。
所以在这一题我们使用队列辅助进行广度优先遍历。每次pop一个元素,就判断其有无左右孩子,若有则将孩子加进队列。
这一题的一个难点是,如何区分层次,使不同层次的数在不同的行上?
遇到这种情况我们一般用一个标记值,而这题的队列存储的是地址。所以我们将NULL设为这个标记值。
作用是:每当一个层次的数全部pop()后,紧随其后的就是NULL。也就是在队列中用NULL把各个层次分开。
我们首先初始的时候在root后加一个NULL。之后的过程中每读到一个NULL就push一个新的NULL。
class Solution
{
public:
vector<vector<int>> levelOrder(TreeNode *root)
{
if (root == NULL)
return {};
vector<vector<int>> ans;
queue<TreeNode *> temp;
temp.push(root);
temp.push(NULL);
vector<int> cur_vec;
while(!temp.empty()){
TreeNode *t = temp.front();
temp.pop();
if(t==NULL){
ans.push_back(cur_vec);
cur_vec.resize(0);
if(temp.size()>0){
temp.push(NULL);
}
}else{
cur_vec.push_back(t->val);
if(t->left)
temp.push(t->left);
if(t->right)
temp.push(t->right);
}
}
return ans;
}
};