题目链接：

题目描述：

根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

image.png

题目思路：

前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。然后分别对左右子树递归地求解。

5d2e29b4-078b-4202-ae4d-44cd8a2b69df.jpg

代码：

  1. package com.newcoder;
  3. import java.util.HashMap;
  4. import java.util.Map;
  6. /**
  7.  * @author :   weigang
  8.  * @date :   2021/3/12 - 16:40
  9.  * 重建二叉树
  10.  **/
  12. class TreeNode {
  13.       int val;
  14.       TreeNode left;
  15.       TreeNode right;
  16.       TreeNode(int x) { val = x; }
  17. }
  19. public class no4 {
  21.     public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
  22.         TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
  23.         return root;
  24.     }
  25.     //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
  26.     private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
  28.         if(startPre>endPre||startIn>endIn){
  29.             return null;
  30.         }
  32.         TreeNode root=new TreeNode(pre[startPre]);
  34.         for(int i=startIn;i<=endIn;i++){
  35.             if(in[i]==pre[startPre]){
  36.                 root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
  37.                 root.right=reConstructBinaryTree(pre,startPre+i-startIn+1,endPre,in,i+1,endIn);
  38.                 break;
  39.             }
  40.         }
  43.         return root;
  44.     }
  46.     public static void main(String[] args) {
  47.         int[] pre = {1,2,3,4,5,6,7};
  48.         int [] in = {3,2,4,1,6,5,7};
  49.         System.out.println(new no4().reConstructBinaryTree(pre,in));
  52.     }
  56. }

代码分析：

前序遍历的第一个数是根节点，通过找到根节点在中序遍历的索引，就可以判断出根节点的左子树有多少个，继而就可以在前序遍历和中序遍历中拆分出根节点的左子树和右子树。通过代码可知，根节点的左子树有i-startIn 个节点。所以

左子树

  • 在前序遍历中的起始和末尾索引是startPre+1,startPre+i-startIn，
  • 在中序遍历中的起始和末尾索引是startIn,i-1

右子树

  • 在前序遍历中的起始和末尾索引是i-startIn+startPre+1,endPre
  • 在中序遍历中的起始和末尾索引是i+1,endIn