题目描述:
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:
给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回锯齿形层序遍历如下:
[
[3],
[20,9],
[15,7]
]
题源:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
代码:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> ans; vector<int> subans; queue<TreeNode* > Q; if (root==NULL) return ans; Q.push(root); subans.push_back(root->val); ans.push_back(subans); int lnum=1; // 主要记录每层有多少节点,达到一层层的结果 while(!Q.empty()) { subans.clear(); for(int i=0;i<lnum;i++) { TreeNode* p=Q.front(); Q.pop(); if(p->left!=NULL) { Q.push(p->left); subans.push_back(p->left->val); } if(p->right!=NULL) { Q.push(p->right); subans.push_back(p->right->val); } } lnum=subans.size(); if(lnum>0) ans.push_back(subans); } for(int i=0;i<ans.size();i++) if(i%2==1) reverse(ans[i].begin(),ans[i].end()); // 如果层数从0开始计数,那么奇数层节点反一下 return ans; } };