# 依据前序序列和中序序列，重建一颗树（PHP递归实现）

www.MyException.Cn  网友分享于：2015-08-23  浏览：0次

```class TreeNode{
public \$data;
public \$lchild = null;
public \$rchild = null;
public function __construct(\$data='',\$lchild=null,\$rchild=null){
\$this->data = \$data;
\$this->lchild = \$lchild;
\$this->rchild = \$rchild;
}
}```

```    //根据前序和中序，重建一颗树
//\$pre 前序遍历的数组
//\$mid 中序遍历的数组
function buildTree(\$pre,\$mid){
\$cnt = count(\$mid);
if(\$cnt<0) return null;
\$root = \$pre[0];
echo '\$root==='.\$root;
\$node = new TreeNode(\$root);
\$lenL = 0;
for(\$i=0;\$i<\$cnt;\$i++){
if(\$mid[\$i]== \$root){
\$lenL = \$i;
break;
}
}
\$lenR = \$cnt -\$lenL - 1;
if(\$lenL>0) \$node->lchild = buildTree(array_slice(\$pre,1,\$lenL),array_slice(\$mid,0,\$lenL));
if(\$lenR>0) \$node->rchild = buildTree(array_slice(\$pre,\$lenL+1,\$lenR),array_slice(\$mid,\$lenL+1,\$lenR));
return \$node;
}

\$mid = array(4,7,2,1,5,3,8,6);
\$pre = array(1,2,4,7,3,5,6,8);
\$node = buildTree(\$pre,\$mid);
echo '<pre>';
var_dump(\$node);
echo '</pre>';```