https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
这道题有一定难度，学习下如何构建和遍历二叉树。

递归

思路：
对于二叉树的前序遍历，我们知道序列的第一个元素必定是根节点的值，因为序列没有重复的元素，因此中序遍历中可以找到相同的这个元素，而我们又知道中序遍历中根节点将二叉树分成了左右子树两个部分，我们可以发现，数字1是根节点，并将二叉树分成了(247)和(3568)两棵子树，而子树的的根也是相应前序序列的首位，比如左子树的根是数字2，右子树的根是数字3，这样我们就可以利用前序遍历序列找子树的根节点，利用中序遍历序列区分每个子树的节点数。
image.png

  • step 1：先根据前序遍历第一个点建立根节点。
  • step 2：然后遍历中序遍历找到根节点在数组中的位置。
  • step 3：再按照子树的节点数将两个遍历的序列分割成子数组，将子数组送入函数建立子树。

  • step 4：直到子树的序列长度为0，结束递归。

    1. public class Reconstruct_binary_tree {
    2.   public static class TreeNode {
    3.       int val;
    4.       TreeNode left;
    5.       TreeNode right;
    7.       TreeNode(int x) {
    8.           val = x;
    9.       }
    10.   }
    12.   public static void main(String[] args) {
    13.       TreeNode rootNode = reConstructBinaryTree(new int[]{1, 2, 4, 7, 3, 5, 6, 8}, new int[]{4, 7, 2, 1, 5, 3, 8, 6});
    14.       System.out.println("over!");
    15.   }
    17.   public static TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
    18.       //递归结束条件
    19.       if (pre.length == 0 || vin.length == 0) {
    20.           return null;
    21.       }
    23.       TreeNode rootNode = new TreeNode(pre[0]);//根结点
    24.       for (int i = 0; i < vin.length; i++) {
    25.           if (pre[0] == vin[i]) { //遍历找到根结点在中序的位置
    26.                                  rootNode.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(vin, 0, i)); //左子树
    28.                                  rootNode.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(vin, i + 1, vin.length)); //右子树
    29.                                  break;
    30.                                 }
    31.       }
    32.       return rootNode;
    33.   }
    34. }