重建二叉樹
- 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 }
