本篇文章给大家带来的内容是关于php如何实现根据前序和 中序遍历 结果重建 二叉树 （代码），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。
输入某二叉树的 前序遍历 和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
1.前序遍历是中，左，右；中序遍历是左，中，右
2.前序遍历的第一个是根结点，中序遍历数组中从开始到根结点的所有是左子树，可以知道左子树的个数，根结点右边的是右子树
3.前序遍历除去0位置的，从1到左子树个数位置是左子树，其他的是右子树
4.确定四个数组，前序左子树数组，前序右子树数组，中序左子树数组，中序右子树数组；递归调用
reConstructBinaryTree( pre ,in)
if(pre.length) return null//递归终止条件
root=pre[0]
Node=new Node(root)
//在中序中找根结点的位置
p=0
for p;p<pre.length;p++
if in[p]==root break
for i=0;i<pre.length;i++
if i<p
//中序左子树数组
inLeft[]=in[i]
//前序左子树数组
preLeft[]=pre[i+1]
else if i>p
//中序的右子树
in right []=in[i]
//前序的右子树
preRight[]=pre[i]
Node->left=reConstructBinaryTree(preLeft,inLeft)
Node->right=reConstructBinaryTree(preRight,inRight)
return Node
<?php
class TreeNode{
var $val;
var $left = NULL;
var $right = NULL;
function __construct($val){
$this->val = $val;
}
};
function reConstructBinaryTree($pre, $vin){
$len=count($pre);
if($len==0){
return null;
}
$root=$pre[0];
$node=new TreeNode($root);
for($p=0;$p<$len;$p++){
if($vin[$p]==$root){
break;
}
}
$preLeft=array();
$preRight=array();
$vinLeft=array();
$vinRight=array();
for($i=0;$i<$len;$i++){
if($i<$p){
$preLeft[]=$pre[$i+1];
$vinLeft[]=$vin[$i];
}else if($i>$p){
$preRight[]=$pre[$i];
$vinRight[]=$vin[$i];
}
}
$node->left=reConstructBinaryTree($preLeft,$vinLeft);
$node->right=reConstructBinaryTree($preRight,$vinRight);
return $node;
}
$pre=array(1,2,4,7,3,5,6,8);
$vin=array(4,7,2,1,5,3,8,6);
$node=reConstructBinaryTree($pre,$vin);;
var_dump($node);
object(TreeNode)#1 (3) {
[“val”]=>
int(1)
[“left”]=>
object(TreeNode)#2 (3) {
[“val”]=>
int(2)
[“left”]=>
object(TreeNode)#3 (3) {
[“val”]=>
int(4)
[“left”]=>
NULL
[“right”]=>
object(TreeNode)#4 (3) {
[“val”]=>
int(7)
[“left”]=>
NULL
[“right”]=>
NULL
}
}
[“right”]=>
NULL
}
[“right”]=>
object(TreeNode)#5 (3) {
[“val”]=>
int(3)
[“left”]=>
object(TreeNode)#6 (3) {
[“val”]=>
int(5)
[“left”]=>
NULL
[“right”]=>
NULL
}
[“right”]=>
object(TreeNode)#7 (3) {
[“val”]=>
int(6)
[“left”]=>
object(TreeNode)#8 (3) {
[“val”]=>
int(8)
[“left”]=>
NULL
[“right”]=>
NULL
}
[“right”]=>
NULL
}
}
}
以上就是php如何实现根据前序和中序遍历结果重建二叉树（代码）的详细内容
Taking Cephalexin And The Sun
PROPERTIES OF SOUND Sound is a mechanical wave produced by vibrating bodies.
This is used to rule out other active leakage or abnormal blood vessel growth that can lead to blood leakage 7 for NOLVADEX vs
She was also stripped of her citizenship
Patient characteristics and demographics are listed in Table 1 Symptoms of chronic enteritis usually appear 6 to 18 months after radiation therapy ends
Kieth GiPsazRzHOhPrdyA 5 20 2022
Chris Riback That s terrific
For a more complete list of studies, please click on soy protein isolate Rather, the targeting strategy is the single layer of therapeutic index expansion
Studies have shown that acupuncture and gentle stretching and exercise may also help reduce this pain With long term, once daily oral administration, antihypertensive effectiveness is maintained for at least 24 hours Label
It is, for the most part, a cosmetic side effect that is considered unattractive and unappealing, but not life threatening
According to another article, nearly four of every 10 millennials have tattoos
Had a Transvaginal US done in Dec and everything was fine
Because these reactions are reported voluntarily from a population of uncertain size, it is not always possible to reliably estimate a causal relationship to drug exposure
cialis medrol 4mg prospect While the prospect of a Met playoff run is unrealistic right now, the six man rotation will also give CollinsГў team the benefit of not having to shut down Harvey and Wheeler at the end of the season because of innings limits
I also have trigger shot at home, but I know I ovulate on
Of course, that guy Fengyue is getting more and more inscrutable, When has she been able to take away only her soul energy, but leave a person s life and consciousness behind
Or did you just admit defeat
The Messenger of Allah PBUH used to say when he was in distress La ilaha illallahul Azimul Halim
Antidepressants and tamoxifen an unrecognized interaction
Monitor Closely 1 dexmedetomidine and daridorexant both increase sedation
Cataract Surgery After LASIK What to Know
Aerobic and facultative organisms group A beta hemolytic streptococci, Neisseria and Eikenella species
and Shanks, C The situation is dynamic
2 cell left panel and Mac1 Gr1 high mature neutrophil cell right panel output of Jak2 RL vs
But Rats Army is still sourcing good- quality SARMs
Phakic intraocular lenses are implanted in the eye without removing the natural lens
IBC inflammatory breast cancer, locally advanced breast cancer and tumors that are too large for surgical removal initially will be treated by chemotherapy before surgery called neo adjuvant chemotherapy
We are so grateful for each and every one of you