根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。

注意:
你可以假設(shè)樹中沒(méi)有重復(fù)的元素。

例如，給出

前序遍歷 preorder =?[3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：

? ? 3
? ?/ \
? 9 ?20
? ? / ?\
? ?15 ? 7

代碼：

/**

?*?Definition?for?a?binary?tree?node.

?*?public?class?TreeNode?{

?*?????int?val;

?*?????TreeNode?left;

?*?????TreeNode?right;

?*?????TreeNode(int?x)?{?val?=?x;?}

?*?}

?*/

class?Solution?{

????int?preorder[];

????int?inorder[];

????int?count?=?0;

????HashMap<Integer,Integer>?map?=?new?HashMap<Integer,Integer>();

????public?TreeNode?buildTree(int[]?preorder,?int[]?inorder)?{

????????this.preorder?=?preorder;

????????this.inorder?=?inorder;

????????int?i?=?0;

????????for(int?x:inorder){

????????????map.put(x,i++);

????????}

????????TreeNode?head?=?helper(0,inorder.length);

????????return?head;

????}

????public?TreeNode?helper(int?left,int?right){

????????if(left==right){

????????????return?null;

????????}

????????int?root_val?=?preorder[count];

????????TreeNode?root?=?new?TreeNode(root_val);

????????count++;

????????int?index?=?map.get(root_val);//分離左右子樹的界限

????????root.left?=?helper(left,index);

????????root.right?=?helper(index+1,right);

????????return?root;

????}

}

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的Leetcode--105. 从前序与中序遍历序列构造二叉树（Java）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。