online advertising

Thursday, July 9, 2015

LeetCode OJ - Construct Binary Tree from Inorder and Postorder Traversal

Problem:

Please find the problem here.

Solution:

This is basically the same as the previous post, except we will take the root as the last element of post order.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

#include "LEET_CONSTRUCT_BINARY_TREE_FROM_INORDER_AND_POSTORDER_TRAVERSAL.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_CONSTRUCT_BINARY_TREE_FROM_INORDER_AND_POSTORDER_TRAVERSAL
{
    struct TreeNode
    {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

    class Solution
    {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
        {
            return buildTree(inorder, 0, inorder.size(), postorder, 0, postorder.size());
        }
    private:
        TreeNode* buildTree(vector<int>& inorder, unsigned int inorderStart, unsigned int inorderEnds, vector<int>& postorder, unsigned int postorderStart, unsigned int postorderEnds)
        {
            if (postorderStart >= postorderEnds)
            {
                return NULL;
            }
            unsigned int inorderIndex = inorderStart;
            for (; inorderIndex < inorderEnds; inorderIndex++)
            {
                if (inorder[inorderIndex] == postorder[postorderEnds - 1])
                {
                    break;
                }
            }
            // inOrder [inorderStart, inorderIndex) is the left subtree.
            // inOrder [inorderIndex + 1, inorderEnds) is the right subtree.
            int leftSubTreeSize = inorderIndex - inorderStart;
            unsigned int postorderIndex = postorderStart + leftSubTreeSize;

            TreeNode* result = new TreeNode(postorder[postorderEnds - 1]);
            result->left = buildTree(inorder, inorderStart, inorderIndex, postorder, postorderStart, postorderIndex);
            result->right = buildTree(inorder, inorderIndex + 1, inorderEnds, postorder, postorderIndex, postorderEnds - 1);

            return result;
        }
    };
};

using namespace _LEET_CONSTRUCT_BINARY_TREE_FROM_INORDER_AND_POSTORDER_TRAVERSAL;

int LEET_CONSTRUCT_BINARY_TREE_FROM_INORDER_AND_POSTORDER_TRAVERSAL()
{
    Solution solution;
    int inorderArray[3] = { 1, 2, 3 };
    int postorderArray[3] = { 1, 3, 2 };
    vector<int> inorder(inorderArray, inorderArray + 3);
    vector<int> postorder(postorderArray, postorderArray + 3);
    TreeNode* result = solution.buildTree(inorder, postorder);
    return 0;
}

No comments :

Post a Comment