## Saturday, November 5, 2016

### LeetCode OJ - Binary Tree Zigzag Level Order Traversal

Problem:

Please find the problem here.

Analysis:

It is relatively easy to just implement BFS, and then reverse the alternate layers, the interesting thing is, we can actually traverse the tree in this zigzag way directly.

Solution:

The key idea is to use a stack instead of a queue for the next layer. If I insert the next layer by the opposite order using a stack, the stack pop will yield exactly what we want - again, note the use of the double buffering technique for the pair of stacks.

Code:

#include "stdafx.h"

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

#include "LEET_BINARY_TREE_ZIGZAG_LEVEL_ORDER_TRAVERSAL.h"
#include <stack>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_BINARY_TREE_ZIGZAG_LEVEL_ORDER_TRAVERSAL
{
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>> result;
stack<TreeNode*> buffer1;
stack<TreeNode*> buffer2;
if (root == nullptr)
{
return result;
}
else
{
stack<TreeNode*>* pBuffer1 = &buffer1;
stack<TreeNode*>* pBuffer2 = &buffer2;
buffer1.push(root);
bool flip = true;
while (true)
{
vector<int> row;
stack<TreeNode*>& last_child = *pBuffer1;
stack<TreeNode*>& this_child = *pBuffer2;
if (last_child.size() == 0)
{
break;
}
while (last_child.size() > 0)
{
TreeNode* current_node = last_child.top();
last_child.pop();
row.push_back(current_node->val);
if (flip)
{
if (current_node->left != nullptr)
{
this_child.push(current_node->left);
}
if (current_node->right != nullptr)
{
this_child.push(current_node->right);
}
}
else
{
if (current_node->right != nullptr)
{
this_child.push(current_node->right);
}
if (current_node->left != nullptr)
{
this_child.push(current_node->left);
}
}
}
result.push_back(row);
flip = !flip;
swap(pBuffer1, pBuffer2);
}

return result;
}
}
};
};

using namespace _LEET_BINARY_TREE_ZIGZAG_LEVEL_ORDER_TRAVERSAL;

int LEET_BINARY_TREE_ZIGZAG_LEVEL_ORDER_TRAVERSAL()
{
Solution solution;
TreeNode a(3);
TreeNode b(9);
TreeNode c(20);
TreeNode d(15);
TreeNode e(7);
a.left = &b;
a.right = &c;
c.left = &d;
c.right = &e;
vector<vector<int>> answer = solution.zigzagLevelOrder(&a);
for (auto&& row : answer)
{
for (auto&& val : row)
{
cout << val << " ";
}
cout << endl;
}
return 0;
}