題目
根據(jù)樹的前序司倚、中序遍歷構(gòu)建出樹結(jié)構(gòu)
題解
什么是前序恨憎、中序我就不帶大家復(fù)習(xí)了 根左右 左根右楞陷。
可愛的小樹
前序遍歷 [3,9,20,15,7]
中序遍歷 [9,3,15,20,7]
- 根據(jù)前序遍歷特點 我們能立刻得知，前序遍歷的第一個元素手报，即是這棵樹的根節(jié)點root節(jié)點眼耀，前序遍歷中 我們可以粗略把數(shù)組內(nèi)容分成3段：根英支、所有左元素、所有右元素（黃根哮伟、綠左干花、藍右）。
前序分隔
- 前序遍歷中楞黄，root節(jié)點的下一個節(jié)點即是第一個左孩子（即節(jié)點9）池凄，那第一個右孩子呢？
- 其實只要能夠計算出左元素個數(shù)我們就能根據(jù)root節(jié)點計算出第一個右孩子在前序遍歷中的相對位置 即
root節(jié)點下標+ 左元素個數(shù) +1即是第一個右孩子下標
中序分隔
- root節(jié)點下標是前序的第一個元素鬼廓，那左元素個數(shù)我們怎么計算呢肿仑？我們不妨找到根節(jié)點在中序遍歷中的下標 他的左側(cè)即是全部左元素，他的右側(cè)即是全部右元素桑阶。例如上圖：我們根據(jù)中序可以發(fā)現(xiàn)root節(jié)點 3左側(cè)有1個元素柏副，那么在前序遍歷中勾邦，從根節(jié)點數(shù)起蚣录，向后數(shù)2位，即是第一個右子樹元素眷篇。
- 此時萎河，我們已經(jīng)能夠構(gòu)建、獲取樹的root蕉饼、第一個左虐杯、第一個右，我們只要把第一個左昧港、第一個右當(dāng)作是新的root擎椰，進行上述邏輯的遞歸，即可構(gòu)建出完整的樹创肥。
- 但是有一點需要注意达舒，在根據(jù)中序計算左右元素數(shù)量的時候應(yīng)當(dāng)控制元素邊界值朋，每次以root將中序數(shù)組分割成3部分，全部左巩搏、root昨登、全部右。
private int [] preorder;
private Map<Integer,Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
map = new HashMap<>(inorder.length);
for (int i=0;i<inorder.length;i++) map.put(inorder[i],i);
return buildTree(0,0,preorder.length-1);
}
private TreeNode buildTree(int rootIndexForPre,int startIndexForIn,int endIndexForIn){
if(startIndexForIn>endIndexForIn) return null;
TreeNode root = new TreeNode(preorder[rootIndexForPre]);
int rootIndexForIn = map.get(preorder[rootIndexForPre]);
root.setLeft(buildTree(rootIndexForPre+1,startIndexForIn,rootIndexForIn-1));
root.setRight(buildTree(rootIndexForIn-startIndexForIn+rootIndexForPre+1,rootIndexForIn+1,endIndexForIn));
return root;
}
源碼: 劍指offer4J
