重建二叉树
- 2019 年 10 月 4 日
- 筆記
本文来自sunandstarws的csdn文章
博客地址：https://blog.csdn.net/sunandstarws/article/details/86578080
题目：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：
看到这个题目就明白需要花点时间，上数据结构课的时候，明白了怎么根据前序和中序可以唯一确定一颗二叉树，并且也知道怎么重建，但是要用代码实现起来，还是有点困难，毕竟自己很久没有写了。我知道要实现那种思路，肯定需要借用递归或者归并。但是不是理的很清，后面觉得借鉴别人怎么实现的，看完之后，决定自己动手，最开始用java编写，写完之后，出现空指针异常和数组非法访问错误，与别人代码对了很久，最后终于找到错误了，这个题困了我一天。对于空指针异常，自己建立对象或者声明数组的时候最好还是初始化，不要等到后面才想起，数组非法访问是由于自己声明的数组太大，没有很严谨，导致我前面一直找不到自己错在哪，感觉没有越界，把数组大小严格改到题目要求所需之后，就提交成功了，可能之前写C语言写习惯了，没有注意这方面，以后还是严谨一点。用js代码实现比Java要方便很多，比较顺利，虽然也出现错误，但是解决了java坑之后，来解决Js的坑就快很多了；
对于这种题目，主要还是想清楚怎么用递归实现，注意细节
java实现代码：
public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { int len=in.length; if(len==0) return null; TreeNode tree=new TreeNode(pre[0]); int i,temp=-1,j=0; for(i=0;i<len;i++){ if(pre[0]==in[i]){ temp=i; break; } } int[] left=new int[temp]; int[] leftpre=new int[temp]; for(i=0;i<temp;i++){ left[i]=in[i]; leftpre[i]=pre[i+1]; }//左子树 int[] right=new int[len-temp-1]; int[] rightpre=new int[len-temp-1]; for(i=temp+1;i<len;i++){ right[j]=in[i]; rightpre[j]=pre[i]; j++; }//右子树 tree.left=reConstructBinaryTree(leftpre,left); tree.right=reConstructBinaryTree(rightpre,right); return tree; }
JavaScript实现代码：
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function reConstructBinaryTree(pre, vin) { var len=vin.length; if(len==0) return null; var tree=new TreeNode(pre[0]); var i,temp=-1,j=0; for(i=0;i<len;i++){ if(pre[0]==vin[i]){ temp=i; break; } } var left=new Array(temp); var leftpre=new Array(temp); for(i=0;i<temp;i++){ left[i]=vin[i]; leftpre[i]=pre[i+1]; }//左子树 var right=new Array(len-temp-1); var rightpre=new Array(len-temp-1); for(i=temp+1;i<len;i++){ right[j]=vin[i]; rightpre[j]=pre[i]; j++; }//右子树 tree.left=reConstructBinaryTree(leftpre,left); tree.right=reConstructBinaryTree(rightpre,right); return tree; // write code here }
