题目输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
我的解法：
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return fun(pre, in, 0, pre.length,0 ,in.length -1 );
}
private TreeNode fun(int[] pre, int[] in, int preLeftIndex,int preRightIndex, int inLeftIndex, int inRightIndex){
if(inLeftIndex > inRightIndex || preLeftIndex > preRightIndex){
return null;
}
TreeNode root = new TreeNode(pre[preLeftIndex]);
for(int i = inLeftIndex; i <= inRightIndex; i++){
if(in[i] == pre[preLeftIndex]){
root.left = fun(pre, in, preLeftIndex + 1, preLeftIndex + i - inLeftIndex, inLeftIndex, i - 1 );
root.right = fun(pre, in, preLeftIndex + i - inLeftIndex + 1, preRightIndex,i + 1, inRightIndex);
break;
}
}
return root;
}
}
思路：
二叉树的前序遍历和中序遍历
- 前序遍历：先访问当前节点，然后以前序访问左子树，右子树。
- 中序遍历：先以中序遍历左子树，接着访问当前节点，然后以中序遍历右子树。
所以前序遍历的特点为：前序遍历的每一个节点都是当前子树的根节点，同时，以中序遍历中该节点为边界，可以把中序遍历的结果分为左子树和右子树
- 前序遍历序列{*1,2,4,7,3,5,6,8}
- 中序遍历序列{4,7,2,*1,5,3,8,6}
前序遍历的第一个节点将中序遍历的结果分成了{4,7,2}和{5,3,8,6}两部分，他就是以1为根的左右两个子树的全部节点
然后接着将其子树按照上述方法进行拆分，就可以获得原始的树结构了。
注：此种解法要保证在树中无重复节点
几个需要注意的点：
- 边界检查
- 如过要想复原一颗二叉树，需要知道他的前/后序遍历+中序遍历 因为前序和后序本质上是一样的，只有应用两种性质不一致的方式才能复原二叉树。
