题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
解答1 :递归实现
/**
* @param pre 前序遍历
* @param in 中序遍历
* @return 二叉树根节点
*/
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
/*
* 输入合法性判断, 不能为空,先序和后序长度要一致
*/
if (pre == null || in == null || pre.length != in.length) {
return null;
}
return construct(pre, 0, pre.length - 1, in, 0, in.length - 1);
}
/**
* @param preArray 前序遍历
* @param preStart 前序遍历的开始位置
* @param preEnd 前序遍历的结束位置
* @param inArray 中序遍历
* @param inStart 中序遍历的开始位置
* @param intEnd 中序遍历的结束位置
* @return 数的根节点
*/
private TreeNode construct(int[] preArray, int preStart, int preEnd, int[] inArray, int inStart, int intEnd) {
if (preStart > preEnd) {
return null;
}
// 取前序遍历的第一个数字就是根节点
int value = preArray[preStart];
// 在中序遍历中中寻找根节点
int index = inStart;
while (index <= intEnd && value != inArray[index]) {
index++;
}
// 如果在整个中序遍历的数组中没有找到,说明输入的参数是不合法的,抛出异常
if (index > intEnd) {
throw new RuntimeException("Invalid Iuput!");
}
// 创建当前根节点,并为根节点赋值
TreeNode node = new TreeNode(value);
// 左子树大小 = 中序中根节点位置 -中序中起始位置
int leftTreeSize = index - inStart;
// 递归调用构建当前节点的左子树
node.left = construct(preArray, preStart + 1, preStart + leftTreeSize, inArray, inStart, index - 1);
// 递归调用构建当前节点的右子树
node.right = construct(preArray, preStart + leftTreeSize + 1, preEnd, inArray, index + 1, intEnd);
return node;
}
网友评论