LeetCode之重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

• 我的答案

  public class Solution {
      public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
          if(pre[0]==0) return null;
          int root = pre[0];
          TreeNode rootNode = new TreeNode(root);
          int index=0;
          while(in[index]!=root){
              index++;
          }
         int[] preL = new int[index>0?index:1];
          int[] preR = new int[(in.length - 1 - index)>0?(in.length - 1 - index):1];
          int[] inL = new int[index>0?index:1];
          int[] inR = new int[(in.length - 1 - index)>0?(in.length - 1 - index):1];
  
      for (int j = 1; j <= index; j++) {
              preL[j - 1] = pre[j];
              inL[j - 1] = in[j - 1];
          }
          for (int i = 0; i <(in.length - 1 - index) ; i++) {
              preR[i] = pre[index + i+1];
              inR[i] = in[index + i+1];
          }
          rootNode.left = reConstructBinaryTree(preL,inL);
          rootNode.right= reConstructBinaryTree(preR,inR);
          return rootNode;
  
      }
  }
  

   

• 标准

  链接：https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6
  来源：牛客网
  
  public class Solution {
      public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
          TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
          return root;
      }
      //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
      private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
  
          if(startPre>endPre||startIn>endIn)
              return null;
          TreeNode root=new TreeNode(pre[startPre]);
  
          for(int i=startIn;i<=endIn;i++)
              if(in[i]==pre[startPre]){
                  root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
                  root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
                        break;
              }
  
          return root;
      }
  }