1.題目概述
- 輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果嗡善，請重建出該二叉樹渐北。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}溶其，則重建二叉樹并返回凝垛。
2.解題思路
- 前序排列順序為 根-左-右，中序排列為左-根-右窗悯。
- 那么如題根為1区匣。
- 則根據(jù)中序遍歷序列則可以得到左子樹{4,7,2,}和右子樹{5,3,8,6}。
- 又根據(jù)前序遍歷則可以得到左子樹的根為2蒋院，右子樹的根為3亏钩。
- 重復(fù)3,4步。
-
直到左右子樹皆為空時即可重建二叉樹如圖欺旧。
- 這是種遞歸思路姑丑，將問題子樹問題遞歸到最后只有三個元素的子樹上。
3.代碼
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode root =re(pre,0,pre.length-1,in,0,in.length-1);//傳入前序遍歷和中序遍歷的序列辞友，返回還原的二叉樹栅哀。
return root;
}
public TreeNode re(int[] pre,int startPre,int endPre,int[] in,int startIn,int endIn){
if(startPre>endPre||startIn>endIn){//判定是否序列是否便利完。
return null;
}
TreeNode root =new TreeNode(pre[startPre]);//存入節(jié)點
for(int i=startIn;i<=endIn;i++){//從中序遍歷開始称龙，尋找和根節(jié)點相同的元素留拾。
if(in[i]==pre[startPre]){//找到了之后分為左右子樹，遞歸進(jìn)行查找茵瀑。
root.left=re(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
root.right=re(pre,startPre+i-startIn+1,endPre,in,i+1,endIn);
}
}
return root;
}
}
