java实现重建二叉树

java实现重建二叉树题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。思路:根据题目给出的前序遍历、后序遍历数组,首先找出根节点然后再根据中序遍历找到左子树和右子树的长度,分别构造出左右子树的前序遍历和中序遍

大家好,又见面了,我是你们的朋友全栈君。

题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

思路:根据题目给出的前序遍历、后序遍历数组,首先找出根节点

然后再根据中序遍历找到左子树和右子树的长度,分别构造出左右子树的前序遍历和中序遍历序列

最后分别对左右子树采取递归,递归跳出的条件是序列长度为1.

比如根据题目的例子,我们由前序遍历先得到了根节点1,然后根据中序遍历,得到左子树的节点应该为{4,7,2},右子树的节点应该为{5,3,8,6}

递归对左子树处理,左子树{4,7,2}的根节点由前序遍历可得为2,那么他的左右子树由中序遍历可得为{4,7}和{} ,对{4,7}处理,可得跟节点为4,左右子树为{},{7} ,处理完毕

递归对右子树处理,右子树{5,3,8,6}的根节点为3,得到左右子树为{5}和{8,6} ,对{8,6}处理,得到根节点为6,左右子树为{8}和{} ,处理完毕

public class TreeNode{
	int data;
	TreeNode left;
	TreeNode right;
	public TreeNode(int data) {
		super();
		this.data = data;
	}
}


import java.util.HashMap;

/*
 * 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
 * 思路:根据题目给出的前序遍历、后序遍历数组,首先找出根节点
 * 然后再根据中序遍历找到左子树和右子树的长度,分别构造出左右子树的前序遍历和中序遍历序列
 * 最后分别对左右子树采取递归,递归跳出的条件是序列长度为1.
 * */
public class 重建二叉树 {
	 public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
	        if (pre==null || in==null) {
				return null;
			}
	        HashMap<Integer, Integer> map=new HashMap<>();//中序的节点在哪个位置
	        for(int i=0;i<in.length;i++){
	        	map.put(in[i], i);
	        }
	        return preIn(pre,0,pre.length-1,in,0,in.length-1,map);
	 }
	 public TreeNode preIn(int[] p,int pi,int pj,int[] n,int ni,int nj,HashMap<Integer, Integer> map){
		 if(pi>pj){
			 return null;
		 }
		 TreeNode head=new TreeNode(p[pi]);
		 int index=map.get(p[pi]);//获得根节点在中序遍历中的位置,由此将中序遍历划分为左右子树,并递归处理
		 head.left=preIn(p,pi+1,pi+(index-ni),n,ni,index-1,map);//(index-ni)为左子树长度
	     head.right=preIn(p,pi+(index-ni)+1,pj,n,index+1,nj,map);//(index-ni+1)为右子树偏移量
	     return head;
	 }
}

C++版

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode *head;
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size()!=vin.size())return nullptr;
        return rec(pre,vin);
    }
    
    TreeNode* rec(vector<int> pre,vector<int> vin){
        if(pre.size()==0 || vin.size()==0) return nullptr;
        TreeNode *node=new TreeNode(pre[0]);
        int mid=find_idx(vin, pre[0]);
        vector<int> left_pre=subv(pre,1,mid);
        vector<int> left_vin=subv(vin,0,mid);
        node->left = rec(left_pre,left_vin);
        
        vector<int> right_pre=subv(pre,mid+1,-2);
        vector<int> right_vin=subv(vin,mid+1,-2);
        node->right = rec(right_pre,right_vin);
        return node;
    }
    
    int find_idx(vector<int> v,int target){
        for(int i=0;i<v.size();i++){
            if(v[i]==target){
                return i;
            }
        }
        return -1;
    }
    
    vector<int> subv(vector<int> v,int start,int end){
        vector<int> r;
        if(end==-2){
            end=v.size()-1;
        }
        for(int i=start;i<=end;i++){
            r.emplace_back(v[i]);
        }
        return r;
    }
};

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130949.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 初识公有云和私有云

    初识公有云和私有云最近刚开始接触云,粗浅记录下来自己的学习。第一个问题:什么是云计算?第二个问题:为什么要上云?第三个问题:公有云和私有云有什么区别,应该怎么选?云计算,是一种按使用量付费的模式,这种模式提供可用的、便捷的、按需的网络访问,进入可配置的计算资源共享池(资源包括网络,服务器,存储,应用软件,服务),这些资源能够被快速提供,只需投入很少的管理工作,或与服务供应商进行很少的交互。【百度百科】举例来讲,建立一个超级数据中心,提高算力,达到普通电脑无法企及的每秒10万亿次的运算能力,一般用户在付费后则可通过

  • C#查询数据库–ExecuteReader方法的使用

    C#查询数据库–ExecuteReader方法的使用在做数据库的查询过程中,使用方法ExecuteReader,其返回结果为MySqlDataReader,由于参考的信息有误,走了好长时间的弯路,记录下来; stringconnectionStr="server=localhost;uid=root;password=;database=db_family";stringsqlContent="select*f…

  • 2021纪念品csgo_csgo最便宜的开箱网站

    2021纪念品csgo_csgo最便宜的开箱网站2021已知目前最全的国内CSGO开箱网站大全!!incsgo国内CSGO饰品皮肤开箱网站官方链接:www.incsgo.gg注册登录自动免费获得$1.00美金取回状态:直接取回**优惠码:**csgogo(充值使用csgogo可增加5%充值金额)skinsdog狗网CSGO饰品皮肤开箱网站可直接取回官方链接:skinsdog.cc注册登录自动免费获得$0.8美金取回状态:直接取回**优惠码:**csgogo(注册使用送0.8美金)coolkaixiang.

  • Time Wait的作用、原因、影响和如何避免

    Time Wait的作用、原因、影响和如何避免TIME_WAIT示例图:1、time_wait的作用:TIME_WAIT状态存在的理由:1)可靠地实现TCP全双工连接的终止  在进行关闭连接四次挥手协议时,最后的ACK是由主动关闭端发出的,如果这个最终的ACK丢失,服务器将重发最终的FIN,因此客户端必须维护状态信息允许它重发最终的ACK。如果不维持这个状态信息,那么客户端将响应RST分节,服务器将此分节解释成一个错误(…

  • java的outputstream_java输入流

    java的outputstream_java输入流我有这个InputStream:InputStreaminputStream=newByteArrayInputStream(myString.getBytes(StandardCharsets.UTF_8));如何将其转换为ServletInputStream?我努力了:ServletInputStreamservletInputStream=(ServletInputStrea…

  • 最火的C语言编程软件,适合编写C语言代码的编程软件有哪些

    最火的C语言编程软件,适合编写C语言代码的编程软件有哪些C语言基本上是大学计算机及其相关专业在大一上学期就会开的一门课程,但是很多学生就是在大一上学期期末的时候很着急,因为自己完全没有学好C语言,感觉一学期白学了,其实究其主要原因,还是因为你在上课认真听了,也做了课堂作业,但是却没有在课后好好的自己去主动敲代码,笔者不能让你有多主动去自己实践,但是笔者可以给你介绍几款更好的写代码的软件(手机电脑都可以)。C语言作为一门起源比较早的编程语言,可以编程的手…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号