怎樣實現重建python二叉樹

今天就跟大家聊聊有關怎樣實現重建python二叉樹，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。

題目：

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列{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
}

看完上述內容，你們對怎樣實現重建python二叉樹有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。