大家好,又见面了,我是你们的朋友全栈君。
题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{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账号...