4.1 题目
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如:
前序遍历序列{ 1, 2, 4, 7, 3, 5, 6, 8 } 根、左、右
中序遍历序列{ 4, 7, 2, 1, 5, 3, 8, 6 } 左、根、右
重建二叉树并输出它的头结点。
4.2 解题思路
- 由前序遍历的第一个节点可知根节点。
- 根据根节点,可以将中序遍历划分成左右子树。
- 在前序遍历中找出对应的左右子树,其第一个节点便是根节点的左右子节点。
- 按照上述方式递归便可重建二叉树。
4.3 实现代码
public class Test {
/**
* 二叉树节点类
*/
public static class BinaryTreeNode {
int value;
BinaryTreeNode left; //左节点
BinaryTreeNode right; //右节点
}
/**
* 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二节树。
* 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
* @param preorder 前序遍历
* @param inorder 中序遍历 //后序遍历 postorder
* @return 树的根结点
*/
public static BinaryTreeNode construct(int[] preorder, int[] inorder) {
// 输入的合法性判断,两个数组都不能为空,并且都有数据,而且数据的数目相同
if (preorder == null || inorder == null || //两个数组不能为空
preorder.length != inorder.length || inorder.length < 1) { //长度要一样。长度不能为0
return null;
}
return construct(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1); //返回另一个重建方法
}
/**
* 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二节树。
* 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
* @param preorder 前序遍历
* @param ps 前序遍历的开始位置
* @param pe 前序遍历的结束位置
* @param inorder 中序遍历
* @param is 中序遍历的开始位置
* @param ie 中序遍历的结束位置
* @return 树的根结点
*/
public static BinaryTreeNode construct(int[] preorder, int ps, int pe,
int[] inorder, int is, int ie) {
/**步骤1:安全性判断**/
// 开始位置大于结束位置说明已经没有需要处理的元素了
if (ps > pe) {
return null;
}
/**步骤2:获取根节点在中序遍历的下标位置!**/
// 取前序遍历的第一个数字,就是当前的根结点
int value = preorder[ps]; //根节点拿到手
int index = is; //拿到中序遍历的起始位置下标
// 在中序遍历的数组中找根结点的位置 ,因为中序遍历是左根右,根节点所在位置是区分开左右子树的关键排序
while (index <= ie && inorder[index] != value) {
index++;
}
// 如果在整个中序遍历的数组中没有找到,说明输入的参数是不合法的,抛出异常
if (index > ie) {
throw new RuntimeException("Invalid input");
}
/**步骤3:使用递归构建左子树和右子树。要记一些节点位置**/
// 创建当前的根结点,并且为结点赋值。赋的值为根节点的值!
BinaryTreeNode node = new BinaryTreeNode();
node.value = value;
// 递归构建当前根结点的左子树,左子树的元素个数:index-is+1个
// 左子树对应的前序遍历的位置在[ps+1, ps+index-is]
// 左子树对应的中序遍历的位置在[is, index-1]
node.left = construct(preorder, ps + 1, ps + index - is,
inorder, is, index - 1);
// 递归构建当前根结点的右子树,右子树的元素个数:ie-index个
// 右子树对应的前序遍历的位置在[ps+index-is+1, pe]
// 右子树对应的中序遍历的位置在[index+1, ie]
node.right = construct(preorder, ps + index - is + 1, pe,
inorder, index + 1, ie);
// 返回创建的根结点
return node;
}
}
对树本身就不熟悉,所以用言语再整理一遍。
已知前序、中序,要重建二叉树并输出头节点。所以题目会给一个前序和一个中序的数组。
一定要给中序数组,只给前序和后序的话重建不了。
网友评论