## Monday, September 28, 2015

### LeetCode OJ - Binary Tree Postorder Traversal

Problem:

Solution:

As mentioned in the problem, recursive solution is trivial, so we will try to do it iteratively.

The recursive solution would look like this

Function postorderTraversalImpl(TreeNode* root)
{
0:  if (root == NULL)
{
return;
}
this->postorderTraversalImpl(root->left);
1:  this->postorderTraversalImpl(root->right);
2:  result.push_back(root->val);
return;
}

In order to change this into an iterative algorithm, I simulated the call stack, in particular, I perform these rules:

A function call is replaced by pushing the parameter and return address to the stack, and jump to the function entry point.

A parameter access is replaced by accessing the parameter value of the top of the stack.

A return is replaced by popping the stack frame and jumping to the address

The jump operation could have been coded using goto, but instead I used status flag to redirect the jumps instead. There is a global while loop to jump backwards, and then an address to go flag to redirect to the right line.

With the addressToGo thing, the code look really ugly, sigh, but it works.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/binary-tree-postorder-traversal/

#include "LEET_BINARY_TREE_POSTORDER_TRAVERSAL.h"
#include <stack>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_BINARY_TREE_POSTORDER_TRAVERSAL
{
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
private:
class Frame
{
public:
TreeNode* root;
};

vector<int> result;
stack<Frame> callstack;

void postorderTraversalImpl(TreeNode* root)
{
while (true)
{
{
break;
}
Frame current = callstack.top();
{
if (current.root == NULL)
{
// return;
callstack.pop();
}
else
{
Frame newFrame;
newFrame.root = current.root->left;
callstack.push(newFrame);
// this->postorderTraversalImpl(root->left);
}
}
{
Frame newFrame;
newFrame.root = current.root->right;
callstack.push(newFrame);
// this->postorderTraversalImpl(root->right);
}
{
result.push_back(current.root->val);
// return
callstack.pop();
}
}
}
public:
vector<int> postorderTraversal(TreeNode* root)
{
this->result.clear();
Frame initialFrame;
initialFrame.root = root;
callstack.push(initialFrame);
this->postorderTraversalImpl(root);
return result;
}
};
};

using namespace _LEET_BINARY_TREE_POSTORDER_TRAVERSAL;

int LEET_BINARY_TREE_POSTORDER_TRAVERSAL()
{
Solution solution;
TreeNode a(1);
TreeNode b(2);
TreeNode c(3);
a.right = &b;
b.left = &c;
vector<int> result = solution.postorderTraversal(&a);
for (unsigned int i = 0; i < result.size(); i++)
{
cout << result[i] << " ";
}
cout << endl;
return 0;
}