剑指Offer - PHP重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例
输入:
前序遍历序列{1,2,4,7,3,5,6,8}
中序遍历序列{4,7,2,1,5,3,8,6}
输出：
遍历概念
前序遍历：根结点 —> 左子树 —> 右子树。
中序遍历：左子树 —> 根结点 —> 右子树。
后序遍历：左子树 —> 右子树 —> 根结点。
层次遍历：只需按树的层级从上往下，从左往右遍历即可。
分析
- 按照前序遍历的规则，可知前序遍历序列第一个数为
根节点，即 1。 - 按照中序遍历的规则，可知中序遍历序列中 1 的左边为左子树
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;
* }
* }
*/
/**
* 递归重建二叉树
*
* @param array $pre 前序遍历序列
* @param array $vin 中序遍历序列
*/
function reConstructBinaryTree($pre, $vin)
{
// 递归要注意出口：如果没有前、中序遍历序列，那么就不要递归。
if($pre && $vin) {
$root = new TreeNode($pre[0]); // 根节点
$index = array_search( $pre[0],$vin); // 根节点在中序数组的位置
$root->left = reConstructBinaryTree(array_slice($pre,1,$index),array_slice($vin,0,$index));
$root->right = reConstructBinaryTree(array_slice($pre,$index+1),array_slice($vin,$index+1));
return $root;
}
return null;
}笔记
| 函数 | 说明 |
|---|---|
| array_search(element, array) | 在 array 中搜索 element，如果成功则返回首个相应的键名 |
| array_slice(array, start, length) | 在 array 中取出一段从 start 开始、长度为 length 的子数组 |
关于 LearnKu
粤公网安备 44030502004330号