给你二叉树的根节点root
,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
提示:
- 树中节点数目在范围 [0, 2000] 内
- -100 <= Node.val <= 100
103.二叉树的锯齿形层序遍历
这题在剑指offer里面刷过捏,所以我啪地一下就写完了
简单来说就是个层序遍历的变种,要点有:
- 通过队列当前size来得知当前层有多少个节点
- 根据当前层节点数预先申请相应大小的数组
- 将申请好的数组放入答案中,根据答案中的数组个数判断当前层数
- 如果是奇数层,从前往后填;否则从后往前填
记得层数是从1开始计数的啊,当时就忘记这茬美美越界还愣了半天不知道错哪了
(感觉那个判断当前层数的方法比较巧妙,可以留意一下~
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 41 42 43 44
|
class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> ans; if(root == nullptr){ return ans; } queue<TreeNode*> q; q.push(root); while(!q.empty()){ int sz = q.size(); vector<int> temp(sz, 0); ans.push_back(temp); int n = ans.size(); for(int i = 0; i < sz; ++i){ TreeNode* node = q.front(); q.pop(); if(n & 1){ ans[n - 1][i] = node->val; }else{ ans[n - 1][sz - i - 1] = node->val; } if(node->left){ q.push(node->left); } if(node->right){ q.push(node->right); } } } return ans; } };
|