php如何实现根据前序和中序遍历结果重建二叉树（代码）

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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) //在中序中找根结点的位置 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

 ?phphtml' target='_blank'>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教程

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。