首页 / 更多教程 / 剑指offer--重建二叉树
剑指offer--重建二叉树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer--重建二叉树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1227字，纯文字阅读大概需要2分钟。
内容图文
题目 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路 先画图 分析在二叉树的前序遍历序列中，第一个数字总是树的根节点的值。但在中序遍历中，根节点的值在序列的中间，左子树的节点的值位于根节点的值得左边，而右子树的节点的值位于根节点的值的右边。
自己写的low代码
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre==null||pre.length==0||in ==null||in.length==0) {
return null;
}
TreeNode root = new TreeNode(pre[0]);
int flag = -1;
for(int i=0;i<in.length;i++) {
if(in[i]==root.val) {
flag = i;
break;
}
}
int[] preLeft = new int[flag];
int[] preRight = new int[in.length-flag-1];
int[] inLeft = new int[flag];
int[] inRight =new int[in.length-flag -1];
for(int i=1;i<=flag;i++) {
preLeft[i-1]=pre[i];
}
for(int i=flag+1;i<in.length;i++) {
preRight[i-flag-1]=pre[i];
}
for(int i=0;i<flag;i++) {
inLeft[i]=in[i];
}
for(int i=flag+1;i<in.length;i++) {
inRight[i-flag-1]=in[i];
}
root.left = reConstructBinaryTree(preLeft,inLeft);
root.right =reConstructBinaryTree(preRight,inRight);
return root;
}
}
原文：https://www.cnblogs.com/LynnMin/p/9388257.html
内容总结
以上是互联网集市为您收集整理的剑指offer--重建二叉树全部内容，希望文章能够帮你解决剑指offer--重建二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。