輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列{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教程

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。