首页 > 代码库 > Binary Tree Zigzag Level Order Traversal
Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes‘ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
3 / 9 20 / 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7]]
代码：
1 class Solution { 2 public: 3 vector<vector<int> > zigzagLevelOrder(TreeNode *root) { 4 vector<vector<int>> res; 5 if(!root) return res; 6 vector<TreeNode *> prev; 7 vector<TreeNode *> cur; 8 cur.push_back(root); 9 bool even = true;10 while(!cur.empty()){11 vector<int> lev_res;12 if(even){13 for(vector<TreeNode *>::iterator it = cur.begin(); it != cur.end(); it++)14 lev_res.push_back((*it)->val);15 }else{16 for(vector<TreeNode *>::reverse_iterator rit = cur.rbegin(); rit != cur.rend(); rit++)17 lev_res.push_back((*rit)->val);18 }19 res.push_back(lev_res);20 even ^= true;21 prev = cur;22 cur.clear();23 for(auto i: prev){24 if(i->left) cur.push_back(i->left);25 if(i->right) cur.push_back(i->right);26 }27 }28 return res;29 }30 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。