php 已知前中序重构二叉树

本文主要是介绍php 已知前中序重构二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

已知先序遍历与中序遍历，可以确定重建一颗二叉树，本例用php演示

题面

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

上图演示了先序遍历 根->左子->右子， 中序遍历 左子->根–>右子

分析

• 分治的思想来解决
• 根据先序遍历，可知道根节点就是给定数组的第一个元素pre[0]
• 以在中序遍历中找出值等于pre[0]的位置，该位置的前半部分就是左子树，右半部分就是右子树
• 重复上述二步，直到递归遍历完成

需要注意的是，可能存在空结点，及使用php时数据越界

代码

class TreeNode{var $val;var $left = NULL;var $right = NULL;function __construct($val){$this->val = $val;}
}function reConstructBinaryTree($pre, $vin)
{if(count($pre)<=0 || count($vin)<=0){return NULL;}$pre_index = 0;$root = new TreeNode($pre[$pre_index]);$vin_index = array_search($pre[$pre_index],$vin);if($pre_index+1> count($pre)-1){$root->left=NULL;}else{$root->left = reConstructBinaryTree(array_slice($pre,$pre_index+1,$vin_index),array_slice($vin,$pre_index,$vin_index));}if($vin_index+1>count($vin)-1){$root->right = NULL;}else{$root->right= reConstructBinaryTree(array_slice($pre,$vin_index+1),array_slice($vin,$vin_index+1));}return $root;
}

这篇关于php 已知前中序重构二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---