online advertising

Monday, September 28, 2015

LeetCode OJ - Binary Tree Postorder Traversal

Problem:

Please find the problem here.

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;
            int returnAddress;
        };

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

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

1 comment :

  1. More traversal algorithms http://maskray.me/blog/2014-08-31-binary-tree-traversal

    ReplyDelete