php重建二叉树（函数缺省参数相关的都写在后面，比如array_slice函数中的$length属性，故第一个参数是操作的数组）
一、总结
牛客网和洛谷一样，是真的好用
二、php重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
三、代码
正确代码：
<?php
/*class TreeNode{
var $val;
var $left = NULL;
var $right = NULL;
function __construct($val){
$this->val = $val;
}
}*/
function reConstructBinaryTree($pre, $vin)
{
// write code here
if($pre && $vin){ //1、两个都判断的确比只判断一个要好
$treeRoot = new TreeNode($pre[0]);
$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;
}
}
错误代码：
<?php
/*class TreeNode{
var $val;
var $left = NULL;
var $right = NULL;
function __construct($val){
$this->val = $val;
}
}*/
//算法：首先肯定是递归
function reConstructBinaryTree($pre, $vin)
{
$tree = new TreeNode();
if($pre){
//1、在前序和中序节点中找跟节点
$tree->val= $pre[0];
//2、找左子树和右子树，左右子树就又可以这样递归来了
$pos=array_search($pre[0],$vin); //2、在数组中查找array_search()
//2、1 左子树
if($pos>0){
$preLeft = array_slice($pre,1,$pos); //3、截取数组array_slice()
$vinLeft = array_slice($vin,0,$pos-1); //4、第三个参数是截取的数量，所以这里应该是$pos
$tree->left = reConstructBinaryTree($preLeft,$vinLeft);
}
//2.2右子树
if(count($vin)>pos+1){
$preRight = array_slice($pre,$pos+1);
$vinRight = array_slice($vin,$pos+1);
$tree->right = reConstructBinaryTree($preRight,$vinRight);
}
}
return $tree;
}
四、参考
1、array_search
array_search
(PHP 4 >= 4.0.5, PHP 5, PHP 7)
array_search — 在数组中搜索给定的值，如果成功则返回首个相应的键名
说明¶
大海捞针，在大海（haystack）中搜索针（ needle 参数）。
参数¶
needle-
搜索的值。
Note:
如果
needle是字符串，则比较以区分大小写的方式进行。 haystack-
这个数组。
strict-
如果可选的第三个参数
strict为TRUE，则 array_search() 将在haystack中检查完全相同的元素。 这意味着同样严格比较haystack里needle的 类型，并且对象需是同一个实例。
返回值¶
如果找到了 needle 则返回它的键，否则返回 FALSE。
如果 needle 在 haystack 中出现不止一次，则返回第一个匹配的键。要返回所有匹配值的键，应该用 array_keys()加上可选参数 search_value 来代替。
更新日志¶
| 版本 | 说明 |
|---|---|
| 5.3.0 | As with all internal PHP functions as of 5.3.0, array_search() returns NULL if invalid parameters are passed to it. |
范例¶
Example #1 array_search() 例子
<?php
$array = array(0 => 'blue', 1 => 'red', 2 => 'green', 3 => 'red');
$key = array_search('green', $array); // $key = 2;
$key = array_search('red', $array); // $key = 1;
?>
2、array_slice
array_slice
(PHP 4, PHP 5, PHP 7)
array_slice — 从数组中取出一段
说明¶
$array , int $offset [, int $length = NULL [, bool $preserve_keys= false ]] )array_slice() 返回根据 offset 和 length 参数所指定的 array 数组中的一段序列。
参数¶
array-
输入的数组。
offset-
如果
offset非负，则序列将从array中的此偏移量开始。如果offset为负，则序列将从array中距离末端这么远的地方开始。 length-
如果给出了
length并且为正，则序列中将具有这么多的单元。如果给出了length并且为负，则序列将终止在距离数组末端这么远的地方。如果省略，则序列将从offset开始一直到array的末端。 preserve_keys-
注意 array_slice() 默认会重新排序并重置数组的数字索引。你可以通过将
preserve_keys设为TRUE来改变此行为。
返回值¶
返回其中一段。 如果 offset 参数大于 array 尺寸，就会返回空的 array。
更新日志¶
| 版本 | 说明 |
|---|---|
| 5.2.4 |
length 参数默认值改成 NULL。 现在 length 为 NULL 时，意思是说使用 array 的长度。 之前的版本里， NULL 的 length 的意思是长度为零（啥也不返回）。 |
| 5.0.2 | 增加了可选参数 preserve_keys 。 |
范例¶
Example #1 array_slice() 例子
<?php
$input = array("a", "b", "c", "d", "e");
$output = array_slice($input, 2); // returns "c", "d", and "e"
$output = array_slice($input, -2, 1); // returns "d"
$output = array_slice($input, 0, 3); // returns "a", "b", and "c"
// note the differences in the array keys
print_r(array_slice($input, 2, -1));
print_r(array_slice($input, 2, -1, true));
?>
以上例程会输出：
Array
(
[0] => c
[1] => d
)
Array
(
[2] => c
[3] => d
)