题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解题思路
二叉树，想到还是递归：重建二叉树，重建根节点的左右节点，对于左右节点来说又是重建根...........
已知前序遍历，中序遍历，来重建二叉树。
- 前序序列的首节点是当前序列重构二叉树的根节点
- 根据根节点来划分中序序列，分为左右两部分。
- 根据中序序列划分，在划分前序序列，分为左右两部分的子前序序列
给定：前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
‘1’ 是当前 前序和中序 的根节点；
根据‘1’划分中序为{4,7,2} 和 {5,3,8,6}
根据中序序列的划分，再划分前序 序列为{2,4,7}和{3,5,6,8}
那么得到的前序{2,4,7}和中序{4,7,2} 就是左子树的两个序列；前序{3,5,6,8}和中序{5,3,6,8}就是右子树的两个序列
再分别对左右子树进行递归构建。
注意点：就是下标问题，这个地方需要仔细考虑下起止和结束。
对于前序序列是由中序序列的划分数目得来的，那么左子树的前序序列 的 结束下标需要减去之前划分出去的。
这个地方笔者也论述不清，建议以 前序{3,5,6,8}和中序{5,3,6,8} 当右子树时候来思考这个地方的下标。
特别注意，起始下标不是0，而是前一轮给定的 前序序列开始 和中序序列开始。
题解
// 二叉树结构
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if (pre != null && in!= null) { // 习惯性防止出现 null传入
TreeNode treeNode = reConstructBinaryTree(pre, in, 0, pre.length - 1, 0, in.length - 1);
return treeNode;
}
return null;
}
private TreeNode reConstructBinaryTree(int[] pre, int[] in, int preS, int preE, int inS, int inE) {
if (preS > preE || inS > inE ) return null;
TreeNode root = new TreeNode(pre[preS]);
for (int i = inS; i <= inE; i++) {
if (in[i] == pre[preS]){
// 当时写的时候就考虑下标了，实际上 长度来理解更方便
// 这个 i-inS 就是中序中 根节点的左侧结点数量
root.left = reConstructBinaryTree(pre,in,preS+1,preS+i-inS,inS,i-1);
root.right = reConstructBinaryTree(pre,in,preS+i+1-inS,preE,i+1,inE);
break;
}
}
return root;
}
