這篇文章帶給大家的內容是關於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 //中序的右子树 inRight[]=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如何實現根據前序和中序遍歷結果重建二元樹(程式碼)的詳細內容。更多資訊請關注PHP中文網其他相關文章!

php把负数转为正整数的方法:1、使用abs()函数将负数转为正数,使用intval()函数对正数取整,转为正整数,语法“intval(abs($number))”;2、利用“~”位运算符将负数取反加一,语法“~$number + 1”。

实现方法:1、使用“sleep(延迟秒数)”语句,可延迟执行函数若干秒;2、使用“time_nanosleep(延迟秒数,延迟纳秒数)”语句,可延迟执行函数若干秒和纳秒;3、使用“time_sleep_until(time()+7)”语句。

php字符串有下标。在PHP中,下标不仅可以应用于数组和对象,还可应用于字符串,利用字符串的下标和中括号“[]”可以访问指定索引位置的字符,并对该字符进行读写,语法“字符串名[下标值]”;字符串的下标值(索引值)只能是整数类型,起始值为0。

php除以100保留两位小数的方法:1、利用“/”运算符进行除法运算,语法“数值 / 100”;2、使用“number_format(除法结果, 2)”或“sprintf("%.2f",除法结果)”语句进行四舍五入的处理值,并保留两位小数。

在php中,可以使用substr()函数来读取字符串后几个字符,只需要将该函数的第二个参数设置为负值,第三个参数省略即可;语法为“substr(字符串,-n)”,表示读取从字符串结尾处向前数第n个字符开始,直到字符串结尾的全部字符。

判断方法:1、使用“strtotime("年-月-日")”语句将给定的年月日转换为时间戳格式;2、用“date("z",时间戳)+1”语句计算指定时间戳是一年的第几天。date()返回的天数是从0开始计算的,因此真实天数需要在此基础上加1。

方法:1、用“str_replace(" ","其他字符",$str)”语句,可将nbsp符替换为其他字符;2、用“preg_replace("/(\s|\ \;||\xc2\xa0)/","其他字符",$str)”语句。

查找方法:1、用strpos(),语法“strpos("字符串值","查找子串")+1”;2、用stripos(),语法“strpos("字符串值","查找子串")+1”。因为字符串是从0开始计数的,因此两个函数获取的位置需要进行加1处理。


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

AI Hentai Generator
免費產生 AI 無盡。

熱門文章

熱工具

ZendStudio 13.5.1 Mac
強大的PHP整合開發環境

SublimeText3 Linux新版
SublimeText3 Linux最新版

MantisBT
Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

Atom編輯器mac版下載
最受歡迎的的開源編輯器

mPDF
mPDF是一個PHP庫,可以從UTF-8編碼的HTML產生PDF檔案。原作者Ian Back編寫mPDF以從他的網站上「即時」輸出PDF文件,並處理不同的語言。與原始腳本如HTML2FPDF相比,它的速度較慢,並且在使用Unicode字體時產生的檔案較大,但支援CSS樣式等,並進行了大量增強。支援幾乎所有語言,包括RTL(阿拉伯語和希伯來語)和CJK(中日韓)。支援嵌套的區塊級元素(如P、DIV),