//題目描述 //輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。 //例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。 //解題思路：前序遍歷的首位是二叉樹根節點 ?通過中序遍歷找到該節點所在位置 ?則其前面的為左子樹 ?后面的為右子樹 ?各個子樹有是同樣的原理 遞歸思想 /*class TreeNode{var $val;var $left = NULL;var $right = NULL;function __construct($val){$this->val = $val;} }*/ function reConstructBinaryTree($pre, $vin) {$root =new TreeNode($pre[0]);//將根節點存入root節點對象$gen = array_search($pre[0], $vin);//根節點在中序遍歷中的位置if($pre && $vin){ $root->left = reConstructBinaryTree( array_slice($pre,1,$gen),array_slice($vin,0,$gen));$root->right = reConstructBinaryTree( array_slice($pre,$gen+1),array_slice($vin,$gen+1));return $root;}}

總結

以上是生活随笔為你收集整理的牛客网（剑指offer） 第四题 重建二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。