未加星标

根据二叉树的前序数组和中序序遍历数组生成二叉树

字体大小 | |
[系统(linux) 所属分类 系统(linux) | 发布者 店小二05 | 时间 20160901 | 作者 红领巾 ] 0人收藏点击收藏

题目:给定二叉树的前序遍历和中序遍历,生成二叉树。

Example:

前序遍历数组:preArr[]:{1,2,4,5,3,6,7}
中序遍历数组:inArr[]:{4,2,5,1,6,3,7}

生成的二叉树如下图:

根据二叉树的前序数组和中序序遍历数组生成二叉树

解题思路:

由二叉树的前序变量性质可知:preArr[0] 是数组的根节点,有根据二叉树的中序遍历的性质可知,{4,2,5}是二叉树的左子树,{6,3,7}在右子树上,重复执行该操作就构造出了二叉树
public class Solution {
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
TreeNode root = new TreeNode(pre[0]);//前序的第一个数定为根
int len = pre.length;
//当只有一个数的时候
if (len == 1) {
root.left = null;
root.right = null;
return root;
}
//找到中序中的根位置
int rootval = root.val;
int i;
for (i = 0; i < len; i++) {
if (rootval == in[i])
break;
}
//创建左子树
if (i > 0) {
int[] pr = new int[i];
int[] ino = new int[i];
for (int j = 0; j < i; j++) {
pr[j] = pre[j + 1];
}
for (int j = 0; j < i; j++) {
ino[j] = in[j];
}
root.left = reConstructBinaryTree(pr, ino);
} else {
root.left = null;
}
//创建右子树
if (len - i - 1 > 0) {
int[] pr = new int[len - i - 1];
int[] ino = new int[len - i - 1];
for (int j = i + 1; j < len; j++) {
ino[j - i - 1] = in[j];
pr[j - i - 1] = pre[j];
}
root.right = reConstructBinaryTree(pr, ino);
} else {
root.right = null;
}
return root;
}
public static void main(String[] args) {
int[] preArr = {1, 2, 4, 5, 3, 6, 7};
int[] inArr = {4, 2, 5, 1, 6, 3, 7};
Solution s = new Solution();
TreeNode root = s.reConstructBinaryTree(preArr, inArr);
s.postOrder(root);
}

本文地址:http://www.linuxidc.com/Linux/2016-09/135514.htm


根据二叉树的前序数组和中序序遍历数组生成二叉树

本文系统(linux)相关术语:linux系统 鸟哥的linux私房菜 linux命令大全 linux操作系统

主题: Linux变量
分页:12
转载请注明
本文标题:根据二叉树的前序数组和中序序遍历数组生成二叉树
本站链接:http://www.codesec.net/view/483449.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 系统(linux) | 评论(0) | 阅读(24)