前序与中序还原树

    class {
        var $val;
        var $left = NULL;
        var $right = NULL;
        function __construct($val){
            $this->val = $val;
        }
    }
    function reConstructBinaryTree($pre, $vin)
    {
        
        if($pre && $vin){
            //前序遍历的第一个节点一定是根节点
            $treeRoot = new TreeNode($pre[0]);
            //index判断根节点在中序中是否存在,并返回根节点在vin中的键名
            $index = array_search($pre[0],$vin);
            $treeRoot->left=reConstructBinaryTree(array_slice($pre,1,$index),array_slice($vin,0,$index));
            $treeRoot->right = reConstructBinaryTree(array_slice($pre,$index+1),array_slice($vin,$index+1));
            return $treeRoot;
        }
    }
$pre = [1,2,4,7,3,5,6,8];
$vin = [4,7,2,1,5,3,8,6];
$re = reConstructBinaryTree($pre, $vin);