剣指offerの面接試験問題6は二叉の木を再建します.

原文のリンク
剣指オフ 二叉の木を再建する
提出URL:  http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157
またはleetcode 105:  https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
参加人数:5246 時間制限:1秒 空間制限:32768 K
テーマの説明
二叉の木の前の順序と中の順序が巡回した結果を入力して、二叉の木を再構築してください.入力された前の順序と中の順序を巡回した結果には重複した数字が含まれていないと仮定します.例えば、シーケンス｛1,2,4,7,3,5,6,8｝と中順序巡回シーケンス｛4,7,2,1,5,3,8,6｝を入力すると、二叉ツリーを再構築して戻ります.
分析:

図に示すように、ルートノードの位置inRootposは、中間シーケンスにおいて最初に発見され、次にルートノードの左側から再帰的に左サブツリーが生成され、ルートノードの右側から再帰的に右サブツリーが生成される.
そのうちpreRootposは一つずつ右に移動します.

#include
#include
using namespace std;
struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x):val(x),left(NULL),right(NULL)
	{}
};
class Solution
{
	public:
		struct TreeNode* reConstructBinaryTree(vector pre,vector in)
		{
			if(pre.size()!=in.size()||pre.size()==0||in.size()==0)return NULL;
			else
			{
				TreeNode* inRoot=createTreeHelper(pre,in,0,0,in.size()-1);
				return inRoot;
			}
		}
		TreeNode* createTreeHelper(vector pre,vector in,int preRootpos,int inLeft,int inRight)
		{//pre:  ,in:  ,preRootpos:       ,inLeft:       ,inRigth:        
			int inRootpos,RootVal;
			RootVal=pre[preRootpos];//      
			//     .at()     
			if(inLeft>inRight) return NULL;
			for(int i=inLeft;i<=inRight;i++)
			{
				if(in[i]==RootVal)
				{
					inRootpos=i;
					//            
					//for          i    ,           
				}
			}
			int leftLen=inRootpos-inLeft;//   inRootpos          
			//leftLen            
			//       
			//              preRootpos+      +1  
			 
			TreeNode* inRoot=new TreeNode(RootVal);
			inRoot->left=createTreeHelper(pre,in,preRootpos+1,inLeft,inRootpos-1);
			inRoot->right=createTreeHelper(pre,in,preRootpos+leftLen+1,inRootpos+1,inRight); 
			return inRoot; 
		}
};
void Intraverse(TreeNode *pRoot)
{
	if(pRoot == NULL) return ;
	Intraverse(pRoot->left);//     
	cout<val<right);//      
}
void PostTraverse(TreeNode *pRoot)
{
	if(pRoot == NULL) return ;
	PostTraverse(pRoot->left);//       
	PostTraverse(pRoot->right);//       
	cout<val< a(arrA,arrA+8);
	vector b(arrB,arrB+8);

	Solution sol;
	TreeNode *root;
	root =sol.reConstructBinaryTree(a,b);
	PostTraverse(root);
	
	return 0;
	
	//    
	//     1 2 4 7 3 5 6 8
	//     4 7 2 1 5 3 8 6
	//       7 4 2 5 8 6 3 1
	
	
	/*
			1
		2      3
	4        5   6 
	 7	        8
	 
	   4 2    
	 7 4    
	 5 3    
	 6 3    
	 8 6     
					
	*/ 
	
}

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector pre,vector vin) {
        if(pre.size()!=vin.size()|| pre.size()<=0||vin.size()<=0 )
        {
            return NULL;
        }
        else
        {
            TreeNode* inRoot=createTree(pre,vin,0,0,vin.size()-1);// inroot     
            return inRoot;
        }
    }
    TreeNode* createTree(vector pre,vector vin,int preroot,int vinleft,int vinright)
    {
        int vinroot,rootval;
        rootval=pre[preroot];//     
         for(int i=vinleft;i<=vinright;i++)
         {
             if(vin[i]==rootval)
             {
                 vinroot=i;
             }
         }
        if(vinleft>vinright) return NULL;
        int leftlen=vinroot-vinleft;//                                    
         
        TreeNode *inRoot=new TreeNode(rootval);
            inRoot->left=createTree(pre,vin,preroot+1,vinleft,vinroot-1);
            inRoot->right=createTree(pre,vin,preroot+leftlen+1,vinroot+1,vinright);
        return inRoot;
         
         
         
         
    }
     
     
     
};