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,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
Solution 1: DFS
in order traversal using DFS and reverse the result of even levels.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua, 0ms, 15.1 MB class Solution { public: vector<vector<int> > zigzagLevelOrder(TreeNode *root) { vector<vector<int>> ans; function<void(TreeNode*, int)> dfs = [&](TreeNode* r, int d) { if (!r) return; while (ans.size() <= d) ans.push_back({}); ans[d].push_back(r->val); dfs(r->right, d + 1); dfs(r->left, d + 1); }; dfs(root, 0); for (int i = 0; i < ans.size(); i += 2) reverse(begin(ans[i]), end(ans[i])); return ans; } }; |
Solution 2: BFS
Expend/append in order for even levels and doing that in reverse order for odd levels.
Time complexity: O(n)
Space complexity: O(n)
C++
|
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 |
// Author: Huahua class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode *root) { if (!root) return {}; vector<vector<int>> ans; deque<TreeNode*> q; q.push_back(root); int d = 0; while (q.size()) { ans.push_back({}); auto cur = &ans.back(); deque<TreeNode*> next; while (q.size()) { if (d % 2) { TreeNode* node = q.back(); q.pop_back(); cur->push_back(node->val); if (node->right) next.push_front(node->right); if (node->left) next.push_front(node->left); } else { TreeNode* node = q.front(); q.pop_front(); cur->push_back(node->val); if (node->left) next.push_back(node->left); if (node->right) next.push_back(node->right); } } ++d; q.swap(next); } return ans; } }; |