class?Solution?{

????/**

?????*?@param?Integer[]?$preorder

?????*?@param?Integer[]?$inorder

?????*?@return?TreeNode

?????*前序遍歷?第一個(gè)是根節(jié)點(diǎn)，在中序數(shù)組中找到根節(jié)點(diǎn)，則中序數(shù)組中左邊的是左子樹(shù)的元素，右邊是右子樹(shù)的元素

?????*然后根據(jù)左右子樹(shù)的元素個(gè)數(shù)也可以將前序數(shù)組分為左右子樹(shù)的前序數(shù)組，以此類(lèi)推。則可以用遞歸來(lái)實(shí)現(xiàn)。

?????*/

????function?buildTree($preorder,?$inorder)?{

????????if(empty($inorder)){

????????????return?null;

????????}

????????$root?=?array_shift($preorder);

????????$qf?=?array_search($root,$inorder);

????????$left_inorder?=?array_slice($inorder,0,$qf);

????????$right_inorder?=?array_slice($inorder,$qf+1);

????????$left_preorder?=?array_slice($preorder,0,count($left_inorder));

????????$right_preorder?=?array_slice($preorder,count($left_inorder));

????????$left?=?$this->buildTree($left_preorder,$left_inorder);

????????$right?=?$this->buildTree($right_preorder,$right_inorder);

????????$root?=?new?TreeNode($root);

????????$root->left?=?$left;

????????$root->right?=?$right;

????????return?$root;

????}

}