코딩테스트 백준 - 2263 트리의 순회

In Order : 	8 4 2 9 5 1 10 6 3 11 7  
Post Order : 	8 4 9 5 2 10 6 11 7 3 1  

          	<--Left--   ---Right-->
In Order : 	8 4 2 9 5 1 10 6 3 11 7
           	<--Left--   ---Right-->
PostOrder : 	8 4 9 5 2 10 6 11 7 3 1

#include <stdio.h>
#include <iostream>

#include <vector>

#include <map>
#include <unordered_map>

using namespace std;

struct Node
{
	Node(int value, Node* left, Node* right)
	{
		this->value = value;
		this->left = left;
		this->right = right;
	}

	int value;
	Node* left;
	Node* right;
};

void CreateTree(const int* inOrder, const int*postOrder, Node** tree, const int& inOrderStartIndex, const int& inOrderEndIndex, const int& postOrderStartIndex, const int& postOrderEndIndex)
{
	if(inOrderStartIndex > inOrderEndIndex)
	{
		return;
	}
	if (postOrderStartIndex > postOrderEndIndex)
	{
		return;
	}

	int root = postOrder[postOrderEndIndex];
	int rootIndex = -1;

	for (int i = inOrderStartIndex; i <= inOrderEndIndex; i++)
	{
		if (root == inOrder[i])
		{
			rootIndex = i;
			break;
		}
	}

	if (*tree == NULL)
	{
		Node* node = new Node(root, NULL, NULL);
		*tree = node;
	}
	
	CreateTree(inOrder, postOrder, &(*tree)->left, inOrderStartIndex, rootIndex - 1, postOrderStartIndex, postOrderStartIndex + (rootIndex - 1 - inOrderStartIndex));
	CreateTree(inOrder, postOrder, &(*tree)->right, rootIndex + 1, inOrderEndIndex, postOrderStartIndex + (rootIndex - inOrderStartIndex), postOrderEndIndex - 1);
}

void PreOrder(Node* tree)
{
	if(tree == NULL) {return;}

	printf("%d ", tree->value);
	PreOrder(tree->left);
	PreOrder(tree->right);

	delete tree;
}

int main()
{
	unordered_map<string, int> um;
	um["SEX"] =0;

	int N;
	cin >> N;
	int* inOrder = new int[N];
	int* postOrder = new int[N];

	for (int i = 0; i < N; i++)
	{
		cin >> inOrder[i];
	}

	for (int i = 0; i < N; i++)
	{
		cin >> postOrder[i];
	}

	Node* tree = NULL;

	CreateTree(inOrder, postOrder, &tree, 0, N-1, 0, N-1);
	PreOrder(tree);

	delete[] inOrder;
	delete[] postOrder;
}