Leetcode 103 Solution

This article provides solution to leetcode question 103 (binary-tree-zigzag-level-order-traversal)

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal

Solution

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> res; queue<TreeNode*> q;
if (root == NULL) return res;
bool dir = true;
q.push(root);
while (q.empty() == false) { vector<TreeNode*> v1; vector<int> v2;
while (q.empty() == false) { v1.push_back(q.front()); q.pop(); }
for (auto it = v1.begin(); it != v1.end(); it++) { if ((*it)->left) q.push((*it)->left); if ((*it)->right) q.push((*it)->right); }
if (dir) { for (auto it = v1.begin(); it != v1.end(); it++) { v2.push_back((*it)->val); } } else if (dir == false) { for (auto it = v1.rbegin(); it != v1.rend(); it++) { v2.push_back((*it)->val); } }
res.push_back(v2);
dir = !dir; }
return res; } };