php重建二叉树（函数缺省参数相关的都写在后面，比如array_slice函数中的$length属性，故第一个参数是操作的数组）
一、总结
牛客网和洛谷一样，是真的好用
二、php重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
三、代码
正确代码：
1 <?php 2 3 /*class TreeNode{ 4 var $val; 5 var $left = NULL; 6 var $right = NULL; 7 function __construct($val){ 8 $this->val = $val; 9 } 10 }*/ 11 function reConstructBinaryTree($pre, $vin) 12 { 13 // write code here 14 if($pre && $vin){ //1、两个都判断的确比只判断一个要好 15 $treeRoot = new TreeNode($pre[0]); 16 $index = array_search($pre[0],$vin); 17 $treeRoot->left = reConstructBinaryTree(array_slice($pre,1,$index),array_slice($vin,0,$index)); 18 $treeRoot->right = reConstructBinaryTree(array_slice($pre,$index+1),array_slice($vin,$index+1)); 19 return $treeRoot; 20 } 21 22 }
错误代码：
1 <?php 2 3 /*class TreeNode{ 4 var $val; 5 var $left = NULL; 6 var $right = NULL; 7 function __construct($val){ 8 $this->val = $val; 9 } 10 }*/ 11 //算法：首先肯定是递归 12 function reConstructBinaryTree($pre, $vin) 13 { 14 $tree = new TreeNode(); 15 if($pre){ 16 //1、在前序和中序节点中找跟节点 17 $tree->val= $pre[0]; 18 //2、找左子树和右子树，左右子树就又可以这样递归来了 19 $pos=array_search($pre[0],$vin); //2、在数组中查找array_search() 20 //2、1 左子树 21 if($pos>0){ 22 $preLeft = array_slice($pre,1,$pos); //3、截取数组array_slice() 23 $vinLeft = array_slice($vin,0,$pos-1); //4、第三个参数是截取的数量，所以这里应该是$pos 24 $tree->left = reConstructBinaryTree($preLeft,$vinLeft); 25 } 26 //2.2右子树 27 if(count($vin)>pos+1){ 28 $preRight = array_slice($pre,$pos+1); 29 $vinRight = array_slice($vin,$pos+1); 30 $tree->right = reConstructBinaryTree($preRight,$vinRight); 31 } 32 } 33 return $tree; 34 }
四、参考
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
)