從兩種遍歷結(jié)果構(gòu)造二叉樹
根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹掂器。
注意:
你可以假設(shè)樹中沒(méi)有重復(fù)的元素俱箱。
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
3
/ \
9 20
/ \
15 7
思路：
兩道題目思路都是相同的狞谱，從前序/后序遍歷的結(jié)果中可以率先確定root，然后在中序遍歷的結(jié)果中找到root跟衅，對(duì)左右子樹進(jìn)行劃分，整個(gè)代碼用遞歸的方式構(gòu)造出二叉樹与斤。
105代碼:
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return bulid(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);//這個(gè)先寫，你傳入的參數(shù)肯定就是這幾個(gè)
}
public TreeNode bulid(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd){
//最后寫遞歸出口 base case撩穿，很簡(jiǎn)單，就是兩個(gè)數(shù)組之一越界就是出口（其實(shí)寫1個(gè)也行食寡，因?yàn)閮蓚€(gè)數(shù)組長(zhǎng)度肯定相同的）
if(preStart > preEnd || inStart > inEnd){
return null;
}
/*先序遍歷框架-根、左抵皱、右*/
//1.先構(gòu)造根節(jié)點(diǎn)的值辩蛋，做根節(jié)點(diǎn)
//2.遞歸構(gòu)造左子樹
//3.遞歸構(gòu)造右子樹
//1.很明顯根節(jié)點(diǎn)的值由先序遍歷數(shù)組的第一個(gè)值確定
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
//2.遞歸構(gòu)造左子樹
// root.left = bulid(preorder, ?, ?, inorder, ?, ?);//移盆？需要我們畫圖去求的悼院，也就是左右子樹的索引
// root.right = bulid(preorder, ?, ?, inorder, ?, ?);//咒循？需要我們畫圖去求的据途，也就是左右子樹的索引
//首先通過(guò)rootVal在inorder中的索引（index）叙甸，然后就能夠知道inorder中左子樹和右子樹的邊界
//可以改進(jìn)的，一開始用hashMap把inorder的值和索引存好裆蒸，到時(shí)候直接查就行。
int index = -1;
for(int i = inStart; i <= inEnd; i++){
if(rootVal == inorder[i]){
index = i;
break;
}
}
//找到了index僚祷，確定inorder中左右子樹的邊界
// root.left = bulid(preorder, ?, ?, inorder, inStart, index - 1);//確定inorder中左子樹的邊界
// root.right = bulid(preorder, ?, ?, inorder, index + 1, inEnd);//確定inorder中右子樹的邊界
//通過(guò)inorder中左子樹節(jié)點(diǎn)的數(shù)目來(lái)確定preorder中左右子樹的邊界
int nums_of_left_tree = index - inStart;
// root.left = bulid(preorder, preStart + 1, preStart + nums_of_left_tree, inorder, ?, ?);//確定preorder中左子樹的邊界
// root.right = bulid(preorder, preStart + nums_of_left_tree + 1, preEnd, inorder, ?, ?);//確定preorder中右子樹的邊界
//最終確認(rèn)好preorder和inorder中的左右子樹邊界
root.left = bulid(preorder, preStart + 1, preStart + nums_of_left_tree, inorder, inStart, index - 1);
root.right = bulid(preorder, preStart + nums_of_left_tree + 1, preEnd, inorder, index + 1, inEnd);
return root;
}
}
106代碼：
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
int len=inorder.length;
return buildTree(inorder,0,len-1,postorder,0,len-1);
}
public TreeNode buildTree(int[] inorder,int inStart,int inEnd,int[] postorder,int postStart,int postEnd){
if(inStart>inEnd||postStart>postEnd){
return null;
}
//后序遍歷的最后一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)
int root = postorder[postEnd];
TreeNode node =new TreeNode(root);
//通過(guò)后序遍歷中確定的根節(jié)點(diǎn)在中序遍歷中確定左右子樹的范圍
int index=0;
for(int i=inStart;i<=inEnd;i++){
if(inorder[i]==root){
index=i;
break;
}
}
node.left=buildTree(inorder,inStart,index-1,postorder,postStart,postStart+index-inStart-1);
node.right=buildTree(inorder,index+1,inEnd,postorder,postEnd-inEnd+index,postEnd-1);
return node;
}
}
