輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)構(gòu)建該二叉樹并返回其根節(jié)點(diǎn)记某。
假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。
示例 1:
????輸入: 前序遍歷數(shù)組preorder = [3,9,20,15,7], ?中序遍歷數(shù)組inorder = [9,3,15,20,7]
????輸出: [3,9,20,null,null,15,7]
解題思路：前序遍歷數(shù)組=[根節(jié)點(diǎn)，[左子樹]，[右子樹]]碳默，中序遍歷數(shù)組=[[左子樹]，根節(jié)點(diǎn)缘眶，[右子樹]]腻窒。
? ? ? ? ? ? ? ? 根節(jié)點(diǎn)root為前序數(shù)組的第一個(gè)節(jié)點(diǎn)值，找到這個(gè)root在中序數(shù)組中的位置磅崭，其中左邊為左子樹，右邊為右子樹瓦哎。
? ? ? ? ? ? ? ? 對(duì)此可使用遞歸操作砸喻，求得root的左右節(jié)點(diǎn)。
/**
?*?Definition?for?a?binary?tree?node.
?*?public?class?TreeNode?{
?*?????int?val;
?*?????TreeNode?left;
?*?????TreeNode?right;
?*?????TreeNode(int?x)?{?val?=?x;?}
?*?}
?*/
class?Solution?{
????public?TreeNode?buildTree(int[]?preorder,?int[]?inorder)?{
????????Map<Integer,?Integer>?hashTable?=?new?HashMap<Integer,?Integer>();//定義一個(gè)map存儲(chǔ)中序遍歷數(shù)組的值下標(biāo)蒋譬，key為值割岛，value為值對(duì)應(yīng)的下標(biāo)，可快速定位到key值對(duì)應(yīng)的下標(biāo)犯助。
????????for(int?i=0;?i<inorder.length;?i++)?{
????????????hashTable.put(inorder[i],?i);//初始化 map
????????}
????????return?dfs(hashTable,?preorder,?inorder,?0,?preorder.length-1,?0,?inorder.length-1);
????}
????public?TreeNode?dfs(Map<Integer,?Integer>?hashTable,?int[]?preorder,?int[]?inorder,?int?preorderLeft,?int?preorderRight,?int?inorderLeft,?int?inorderRight)?{
? ? ? ? // preorderLeft表示前序數(shù)組的對(duì)應(yīng)的子數(shù)組的左下標(biāo)癣漆；
? ? ? ? // preorderRight 表示前序數(shù)組的對(duì)應(yīng)的子數(shù)組的右下標(biāo)；
? ? ? ? // inorderLeft t表示中序數(shù)組的對(duì)應(yīng)的子數(shù)組的左下標(biāo)剂买；
? ? ? ? // inorderRight 表示中序數(shù)組的對(duì)應(yīng)的子數(shù)組的右下標(biāo)惠爽；
????????if(preorderLeft>preorderRight)?{
????????????return?null;
????????}
????????TreeNode?root?=?new?TreeNode(preorder[preorderLeft]); // 根節(jié)點(diǎn)root為前序數(shù)組的第一個(gè)節(jié)點(diǎn)值
????????int?rootIndex?=?hashTable.get(root.val); //?從map中找到這個(gè)root在中序數(shù)組中的位置
????????int?leftTreeSize?=?rootIndex?-?inorderLeft; // 左子樹長(zhǎng)度 = root 在中序數(shù)組中的位置-中序數(shù)組的首下標(biāo)
? ? ? ??
? ? ? ? //root的左節(jié)點(diǎn)=dfs（左子樹）
????????root.left?=?dfs(hashTable,?preorder,?inorder,?preorderLeft+1,?preorderLeft+leftTreeSize,?inorderLeft,?rootIndex-1);
? ?????? ?//root的左節(jié)點(diǎn)=dfs（右子樹）
????????root.right?=?dfs(hashTable,?preorder,?inorder,?preorderLeft+1+leftTreeSize,?preorderRight,?rootIndex+1,?inorderRight);
????????return?root;
????}
}
