首页 > 代码库 > Leetcode | Binary Tree Zigzag Level Order Traversal
Leetcode | 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 void reverse(vector<int> &arr) { 4 for (int i = 0, j = arr.size() - 1; i < j; i++, j--) swap(arr[i], arr[j]); 5 } 6 7 vector<vector<int> > zigzagLevelOrder(TreeNode *root) { 8 vector<vector<int> > ans; 9 if (root == NULL) return ans;10 vector<vector<TreeNode*> > layers(2);11 vector<int> tmp;12 int cur = 0, next = 1;13 layers[cur].push_back(root);14 15 while (!layers[cur].empty()) {16 layers[next].clear();17 tmp.clear();18 for (auto node : layers[cur]) {19 if (node->left) layers[next].push_back(node->left);20 if (node->right) layers[next].push_back(node->right);21 tmp.push_back(node->val);22 }23 if (cur == 1) reverse(tmp);24 ans.push_back(tmp);25 cur = !cur, next = !next;26 }27 28 return ans;29 }30 };
Leetcode | Binary Tree Zigzag Level Order Traversal
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。