剑指offer面试题7:重建二叉树(JAVA版)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer面试题7:重建二叉树(JAVA版),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3008字,纯文字阅读大概需要5分钟。
内容图文
![剑指offer面试题7:重建二叉树(JAVA版)](/upload/InfoBanner/zyjiaocheng/846/2bc8d533863e49109b1f263df550763c.jpg)
题目
输入某二叉树的前序遍历结果和中序遍历结果,请重建该二叉树,假设输入的前序遍历和中序遍历的结果都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。二叉树的节点定义如下:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
思路
在二叉树的前序遍历序列中,第一个数字总是二叉树的根节点的值;在中序遍历的序列中,根节点的值总是在中间,左子树的节点的值位于根节点的值的左边,右子树的节点的值位于根节点的值的右边。
以前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}为例
-
找根节点 首先找到前序遍历序列的第一个值 1 显然是根节点的值。
-
寻找该根节点左右子树节点的值 在中序遍历序列中找到 1的位置,根据中序遍历的特点我们可以知道 1 左边的值(4,7,2)是 根节点值为1的左子树节点的值,1右边的值(5,3,8,6)是 根节点为1 的右子树的节点的值;到此我们可以确定在前序遍历序列中1后面前三个值(2,4,7)是根节点值为1 的左子树的节点值,剩余的值(3,5,6,8)是根节点值为1的右子树的节点的值。知道了左右子树节点的值就可以创建左右子树。
-
创建左子树 对前序遍历序列(2,4,7)和中序遍历序列(4,7,2)执行步骤1和步骤2.直到前序遍历的序列和中序遍历序列都只有一个值时停止执行。
-
创建右子树 对前序遍历序列(3,5,6,8)和中序遍历序列(5,3,8,6)执行步骤1和步骤2.直到前序遍历的序列和中序遍历序列只有一个值时停止执行。
由上面的分析我们可以采取递归来实现该算法
代码实现
/**
* pre[]前序遍历序列 in[] 中序遍历序列 startPre 前序遍历序列的起始位置
* endPre 前序遍历序列的末尾 stratIn 中序遍历序列的起始位置 endIn 中序遍历的末尾
**/
public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
if(pre==null||in==null||in.length<=0) {
return null;
}
return conStructCore(pre,0,pre.length-1,in,0,in.length-1);
}
public TreeNode conStructCore(int[] pre ,int startPre,int endPre,int[] in,int startIn,int endIn)
{
int rootValue=pre[startPre];//得到根节点的值
TreeNode root=new TreeNode(rootValue);//创建根节点
root.left=root.right=null;
if(startPre==endPre)//当前序编列序列和中序遍历序列的值只有一个时停止
{
if(startIn==endIn&&pre[startPre]==in[startIn])
{
return root;
}
}
int rootIn=startIn;//标识根节点的位置
while(rootIn<=endIn&&in[rootIn]!=rootValue)//在中序遍历序列中寻找根节点的位置
{
rootIn++;
}
int leftLength=rootIn-startIn;//得到该根节点的左子树的节点个数
int preEnd=startPre+leftLength;
if(leftLength>0)//创建左子树
{
root.left=conStructCore(pre,startPre+1,preEnd,in,startIn,rootIn-1);
}
if(leftLength<endPre-startPre)//创建右子树
{
root.right=conStructCore(pre,preEnd+1,endPre,in,rootIn+1,endIn);
}
return root;
}
前序遍历递归算法实现
public void preTravel(TreeNode root)
{
if(root==null)
{
return ;
}
System.out.println(root.val);
preTravel(root.left);
preTravel(root.right);
}
中序遍历递归算法实现
public void inTravel(TreeNode root)
{
if(root==null)
{
return ;
}
inTravel(root.left);
System.out.println(root.val);
inTravel(root.right);
}
测试样例
public static void main(String[]args)
{
int[] pre={1,2,4,7,3,5,6,8};
int[] in={4,7,2,1,5,3,8,6};
Test test=new Test();
TreeNode root=test.reConstructBinaryTree(pre,in);
test.preTravel(root);
test.inTravel(root);
}
测试结果
对得到的二叉树进行前序遍历
对得到的二叉树进行中序遍历
内容总结
以上是互联网集市为您收集整理的剑指offer面试题7:重建二叉树(JAVA版)全部内容,希望文章能够帮你解决剑指offer面试题7:重建二叉树(JAVA版)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。