剑指offer——重建二叉树

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

基础概念补充:

前序遍历

首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

中序遍历

首先遍历左子树，然后访问根结点，最后遍历右子树。

后序遍历

首先遍历左子树，然后遍历右子树，最后访问根结点。

解法1：

  /**
   * 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) {
          TreeNode root = reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
          return root;
      }
      public TreeNode reConstructBinaryTree(int[]pre,int pre_l,int pre_r,
                                      int[]in,int in_l,int in_r){
          if(pre_l>pre_r||in_l>in_r){
                  return null;
          }
          TreeNode root = new TreeNode(pre[pre_l]);
          for(int i=in_l;i<=in_r;i++){
              if(in[i]==pre[pre_l]){
                  root.left = reConstructBinaryTree(pre,pre_l+1,pre_l+i-in_l,in,in_l,i-1);
                  root.right = reConstructBinaryTree(pre,pre_l+i-in_l+1,pre_r,in,i+1,in_r);
                  break;
                }
          }
          return root;
      }
}

解法2：

  public class Solution {
      public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
          TreeNode root = new TreeNode(pre[0]);
          int i = 0;
          while(in[i]!=pre[0]){
                    i++;
          }
          root.left = addTree(pre, in, 1, i, 0, i-1);
          root.right = addTree(pre, in, i+1, pre.length-1, i+1, in.length-1);
          return root;
      }
    
      public static TreeNode addTree(int[] pre,int[] in,int pre_l,int pre_r,int in_l,int in_r){
          if(pre_l>pre_r) return null;
              TreeNode root = new TreeNode(pre[pre_l]);
              if(pre_l==pre_r) return root;
          int i = 0;
          while(in[i+in_l]!=pre[pre_l]) i++;
          root.left = addTree(pre, in, pre_l+1, pre_l+i, in_l, in_l+i-1);
          root.right = addTree(pre, in, pre_l+i+1, pre_r, in_l+i+1, in_r);
          return root;
      }
  }

两种方法中心思想其实是一样的.