问题:输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如,输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。
先上代码。
/**
* 重建二叉树
*/
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return core(pre, in, 0,pre.length - 1, 0, in.length - 1);
}
public TreeNode core(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd){
// 根节点(前序遍历的第一个节点)
int rootVal = pre[preStart];
TreeNode root = new TreeNode(rootVal);
// 找到根节点在中序遍历数组中的位置
int rootIndexIn = inStart;
for(;rootIndexIn <= inEnd; rootIndexIn++){
if(in[rootIndexIn] == rootVal)
break;
}
// 计算左子树的长度
int leftLen = rootIndexIn - inStart;
// 计算右子树的长度
int rightLen = inEnd - rootIndexIn;
if(leftLen > 0){
// 存在左子树
// 找到左子树的中序遍历数组
int leftInStart = inStart;
int leftInEnd = leftInStart + leftLen - 1;
// 找到左子树的前序遍历数组
int leftPreStart = preStart + 1;
int leftPreEnd = leftPreStart + leftLen - 1;
// 构建左子树
root.left = core(pre,in,leftPreStart, leftPreEnd, leftInStart, leftInEnd);
}
if(rightLen > 0){
// 存在右子树
// 找到右子树的中序遍历数组
int rightInStart = rootIndexIn + 1;
int rightInEnd = rightInStart + rightLen - 1;
// 找到右子树的前序遍历数组
int rightPreStart = preEnd - rightLen + 1;
int rightPreEnd = preEnd;
// 构建右子树
root.right = core(pre, in, rightPreStart, rightPreEnd, rightInStart, rightInEnd);
}
return root;
}
关于树的问题很多都可以使用递归的方式解决,只要将一般化的处理过程想清楚,再把返回条件搞好,基本就可以。本题已知二叉树的前序遍历和中序遍历结果,找出根节点的值,然后再根据这个值找出左子树和右子树对应的前序和中序遍历结果,就可以进行递归编程了。此题比较麻烦的子树数组的界限问题,处理好这个问题,递归也就不会出错了。
详细的解题流程在注释里已经比较清楚,不再赘述。
网友评论