leetcode_105번 - Construct Binary Tree from Preorder and Inorder Traversal(트리, 귀속)

Construct Binary Tree from Preorder and Inorder Traversal

 
Total Accepted: 32279 Total Submissions: 122094 My Submissions
Question
 Solution 
 
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:You may assume that duplicates do not exist in the tree.
 
Hide Tags
 
Tree   Array   Depth-first Search
Have you met this question in a real interview? 
Yes
 
No
 
Discuss
이 문제는 두 갈래 나무의 앞차례 역주행과 중간차례 역주행의 결과(vector 형식으로 주었는데 그 중에는 존재하지 않는 점이 없음)를 주었기 때문에 앞차례 역주행에서 첫 번째는 뿌리 노드가 틀림없다
이 문제는 차례차례 방법으로 한다. 왜냐하면 앞차례 차례차례 중의 첫 번째 점, 중간차례 차례차례 차례차례 가운데 왼쪽은 왼쪽 나무, 오른쪽은 오른쪽 나무이기 때문이다. 이렇게 차례차례 아래로 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례 차례차례
다음은 AC의 해법입니다.

#include<iostream>

#include <vector>

using namespace std;







struct TreeNode {

	     int val;

	     TreeNode *left;

	     TreeNode *right;

	     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

	 };



/* a vec */

int laocation_vector(vector<int>& vec,int a,int i,int j)

{

	for(int k=i;k<=j;++k)

		if(vec[k]==a)

			return k;

	return -1;

}



/*i,j ，k */

void pre_construct(vector<int>& preorder,vector<int>& inorder,TreeNode** root,int i,int j,int& k)

{

	if(k>=preorder.size())

	{

		*root=NULL;

		return;

	}

	int loacte_in=laocation_vector(inorder,preorder[k],i,j);

	if(loacte_in<i||loacte_in>j)

	{

		*root=NULL;

		return;

	}

	*root=(TreeNode*)malloc(sizeof(TreeNode));

	(*root)->val=preorder[k];

	k++;

	pre_construct(preorder,inorder,&(*root)->left,i,loacte_in-1,k);

	pre_construct(preorder,inorder,&(*root)->right,loacte_in+1,j,k);

	return;

}

/* */

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)

{

	TreeNode* root=NULL;

	if(preorder.size()==NULL)

		return root;

	int k=0;

	pre_construct(preorder,inorder,&root,0,(preorder.size()-1),k);

	return root;

}

int main()

{

	vector<int> vec_pre;

	vector<int> vec_in;

	vec_pre.push_back(1),vec_pre.push_back(2);

	vec_in.push_back(2),vec_in.push_back(1);

	TreeNode* root;

	root=buildTree(vec_pre,vec_in);

}