题面
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
例如: 给定二叉树: [3,9,20,null,null,15,7]
,
返回:
限制
思路
BFS层序遍历,加个标记,当一层遍历完时,队列里即是下一层,使用q.back()更新标记即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
|
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int> > ans; vector<int> row; if(root==NULL) return ans;
queue<TreeNode *>q; q.push(root); TreeNode *end = root;
while(!q.empty()){ TreeNode *t = q.front(); q.pop(); row.push_back(t->val); if(t->left) q.push(t->left); if(t->right) q.push(t->right); if(t == end){ ans.push_back(row); row.clear(); end = q.back(); } } return ans; } };
|