首页 > 代码库 > LeetCode:Binary Tree Zigzag Level Order Traversal
LeetCode:Binary Tree Zigzag Level Order Traversal
本题也属于层次遍历的变形，不同之处在于其遍历的方法是交替进行的，形成一个ZigZag的曲线形式，如下：
代码如下：
1 struct TreeNode { 2 int val; 3 TreeNode* left; 4 TreeNode* right; 5 TreeNode(int x): val(x), left(NULL),right(NULL) {} 6 }; 7 8 void Swap(vector<int> &ivec) 9 {10 int temp = 0;11 int len = ivec.size();12 for (int i = 0; i < len/2; i ++) {13 temp = ivec.at(i);14 ivec.at(i) = ivec.at(len-1-i);15 ivec.at(len-1-i) = temp;16 }17 }18 19 vector<vector <int> > zigzagLevelOrder(TreeNode *root)20 {21 vector<vector<int> > tree_vector;22 vector<int> ivec;23 queue<TreeNode *> tree_queue;24 if (NULL == root)25 return tree_vector;26 27 tree_queue.push(root);28 tree_queue.push(NULL);29 int nLevelCount = 1;30 while (true) {31 TreeNode *pTemp = tree_queue.front();32 tree_queue.pop();33 if (pTemp == NULL) {34 if (nLevelCount%2 == 0) { //if the num of level is odd, swap the ivec;35 Swap(ivec);36 }37 tree_vector.push_back(ivec);38 ivec.clear();39 if (tree_queue.empty())40 break;41 tree_queue.push(NULL);42 nLevelCount ++;43 }44 else {45 ivec.push_back(pTemp->val);46 if (pTemp->left)47 tree_queue.push(pTemp->left);48 if (pTemp->right)49 tree_queue.push(pTemp->right);50 }51 }52 return tree_vector;53 }
LeetCode:Binary Tree Zigzag Level Order Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。