問題描述
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果擅憔，請重建出該二叉樹橡淑。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字掂之。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}店诗，則重建二叉樹并返回岭埠。
思路：
![Uploading 2016427100615131_321824.png . . .]
- 首先根據(jù)前序遍歷確定跟節(jié)點盏混；
- 中序排列中，根節(jié)點的左右內(nèi)容分別是二叉樹左右子樹的內(nèi)容惜论；
- 找到左子樹后许赃，找到左子樹的根節(jié)點；在中序排列中馆类，左子樹根節(jié)點的左右分別包含其左右子樹的內(nèi)容混聊；
- 右子樹按照左子樹的思路進(jìn)行遞歸，最后重建二叉樹蹦掐。
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length == 0 || in.length == 0){
return null;
}
TreeNode node = new TreeNode(pre[0]);
for(int i = 0; i < in.length; i ++){
if(pre[0] == in[i]){
int preLeft[] = new int[i];
int inLeft[] = new int[i];
int preRight[] = new int[pre.length - i - 1];
int inRight[] = new int[in.length - i -1];
for(int j = 0; j < in.length; j ++){
if(j < i){
preLeft[j] = pre[j + 1];
inLeft[j] = in[j];
}
if(j > i){
preRight[j - i -1] = pre[j];
inRight[j - i -1] = in[j];
}
}
node.left = reConstructBinaryTree(preLeft, inLeft);
node.right = reConstructBinaryTree(preRight, inRight);
}
}
return node;
}
}
