题面
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如: 给定二叉树: [3,9,20,null,null,15,7]
,
返回:
限制
思路
BFS层序遍历,加个标记,当一层遍历完时,队列里即是下一层,使用q.back()更新标记即可。
再加个行号判断奇偶,决定是否reverse即可。
代码
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 37 38 39 40
|
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; int line = 0;
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){ if(line & 1) reverse(row.begin(), row.end()); ans.push_back(row); line++; row.clear(); end = q.back(); } } return ans; } };
|