题目

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

题解

利用前序遍历和中序遍历的性质来解决这个问题。 首先前序遍历的第一个节点是树的根节点root，在中序遍历中找到这个root，则root前面就是左子树的中序遍历结果。root后面就是右子树的中序遍历。 同时根据中序遍历可得到左子树的长度。 前序遍历中的第二个节点是左子树的根节点，以此来递归调用。

代码

<?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ function reConstructBinaryTree($pre, $vin) { // write code here return build($pre, $vin, 0, count($pre)-1, 0, count($vin)-1); } function build($pre, $inorder, $pstart, $pend, $istart, $iend) { if ($pstart > $pend||$istart>$iend)return; $root = $pre[$pstart]; for($find = $istart; $find<=$iend;$find++){ if($root === $inorder[$find]){ break; } } $len = $find-$istart;//左子树长度 $res = new TreeNode($inorder[$find]); $res->left = build($pre, $inorder, $pstart+1, $pstart+$len,$istart,$find-1); $res->right = build($pre, $inorder ,$pstart+$len+1, $pend,$find+1, count($inorder)-1); return $res; }