题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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) {
}
分析
根据题目要求可知，传入两个数组，一个是前序遍历序列，一个是中序遍历序列。
二叉树的特性，前序规律：中左右，即第一个元素就是「根节点」；中序规律：左中右，「根节点」在中间，根节点左边的是左子树，根节点右边的是右节点。
1）用前序获取到「根节点」；
2）用「根节点」的值，去扫描中序序列，找出中序根节点的位置（索引值）；
3）在中序找到根节点的位置，那么根节点的左边就是左子树，根节点右边的就是右子树；
4）分别找到了左、右子树的前序遍历序列和中序遍历序列，重复步骤1）2）3），本质就是一个递归过程。
代码
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/*
*@pre 前序遍历数组
*@preStart 前序数组起始位
*@preEnd 前序数组终止位
*@in 中序遍历数组
*@instart 中序遍历数组起始位
*@inEnd 中序遍历数组终止位
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode tree = reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
return tree;
}
//前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
if(startPre > endPre||startIn > endIn){
return null;
}
//前序遍历数组的第一个元素就是子树的根节点
int root = pre[startPre];
TreeNode tree = new TreeNode(root);
//根据【前序遍历数组得到的根节点】在【中序遍历数组】中找到根节点所在的位置
int rootIndex = 0;
for(int i=startIn;i<=endIn;i++){
if(in[i] == root){
rootIndex = i;
//当前根节点，左子树的节点数/右子树的节点数
int leftCount = rootIndex - startIn;
int rightCount = endIn - rootIndex;
//左右子树递归
tree.left = reConstructBinaryTree(pre, startPre+1, startPre+leftCount, in, startIn, rootIndex-1);
tree.right = reConstructBinaryTree(pre, leftCount+startPre+1, endPre, in, rootIndex+1, endIn);
break;
}
}
return tree;
}
}
参考文献：
https://blog.csdn.net/lhl1124281072/article/details/79842315
https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6
