输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
1.前序遍历是中，左，右；中序遍历是左，中，右
2.前序遍历的第一个是根结点，中序遍历数组中从开始到根结点的所有是左子树，可以知道左子树的个数，根结点右边的是右子树
3.前序遍历除去0位置的，从1到左子树个数位置是左子树，其他的是右子树
4.确定四个数组，前序左子树数组，前序右子树数组，中序左子树数组，中序右子树数组；递归调用
reConstructBinaryTree(pre,in)
if(pre.length) return null//递归终止条件
root=pre[0]
Node=new Node(root)
//在中序中找根结点的位置
p=0
for p;p<pre.length;p++
if in[p]==root break
for i=0;i<pre.length;i++
if i<p
//中序左子树数组
inLeft[]=in[i]
//前序左子树数组
preLeft[]=pre[i+1]
else if i>p
//中序的右子树
inRight[]=in[i]
//前序的右子树
preRight[]=pre[i]
Node->left=reConstructBinaryTree(preLeft,inLeft)
Node->right=reConstructBinaryTree(preRight,inRight)
return Node
<?php
class TreeNode{
var $val;
var $left = NULL;
var $right = NULL;
function __construct($val){
$this->val = $val;
}
};
function reConstructBinaryTree($pre, $vin){
$len=count($pre);
if($len==0){
return null;
}
$root=$pre[0];
$node=new TreeNode($root);
for($p=0;$p<$len;$p++){
if($vin[$p]==$root){
break;
}
}
$preLeft=array();
$preRight=array();
$vinLeft=array();
$vinRight=array();
for($i=0;$i<$len;$i++){
if($i<$p){
$preLeft[]=$pre[$i+1];
$vinLeft[]=$vin[$i];
}else if($i>$p){
$preRight[]=$pre[$i];
$vinRight[]=$vin[$i];
}
}
$node->left=reConstructBinaryTree($preLeft,$vinLeft);
$node->right=reConstructBinaryTree($preRight,$vinRight);
return $node;
}
$pre=array(1,2,4,7,3,5,6,8);
$vin=array(4,7,2,1,5,3,8,6);
$node=reConstructBinaryTree($pre,$vin);;
var_dump($node);
object(TreeNode)#1 (3) {
["val"]=>
int(1)
["left"]=>
object(TreeNode)#2 (3) {
["val"]=>
int(2)
["left"]=>
object(TreeNode)#3 (3) {
["val"]=>
int(4)
["left"]=>
NULL
["right"]=>
object(TreeNode)#4 (3) {
["val"]=>
int(7)
["left"]=>
NULL
["right"]=>
NULL
}
}
["right"]=>
NULL
}
["right"]=>
object(TreeNode)#5 (3) {
["val"]=>
int(3)
["left"]=>
object(TreeNode)#6 (3) {
["val"]=>
int(5)
["left"]=>
NULL
["right"]=>
NULL
}
["right"]=>
object(TreeNode)#7 (3) {
["val"]=>
int(6)
["left"]=>
object(TreeNode)#8 (3) {
["val"]=>
int(8)
["left"]=>
NULL
["right"]=>
NULL
}
["right"]=>
NULL
}
}
}
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现的相关教程结束。
