1. import java.util.ArrayList;
    2. import java.util.Arrays;
    4. /**
    5.  * 面试题7：重建二叉树
    6.  * 输入某二叉树的前序遍历和中序遍历的结果，重建该二叉树。假设输入的前序遍历和中序遍历的结果都不含重复的数字
    7.  * 例如，输入前序遍历{1,2,4,7,3,5,6,8}和中序遍历{4,7,2,1,5,3,8,6}
    8.  * 重建并输出头节点
    9.  */
    10. public class No7 {
    12.     //递归（传入数组拷贝）
    13.     public static BinaryTree reConstructBinaryTree(int[] pre, int[] in) {
    14.         //首先考虑测试用例
    15.         //（1）普通二叉树（完全二叉树，不完全二叉树）
    16.         //（2）特殊二叉树（所有节点都没有左（右）节点的二叉树，只有一个节点的二叉树）
    17.         //（3）特殊输入用例（前序遍历和中序遍历不匹配，根节点为null）
    18.         if (pre == null || in == null || in.length == 0 || in.length != pre.length) {
    19.             return null;
    20.         }
    22.         BinaryTree root = new BinaryTree(pre[0]);
    23.         for (int i = 0; i < pre.length; i++) {
    24.             if (pre[0] == in[i]) {
    25.                 root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
    26.                 root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
    27.             }
    28.         }
    29.         return root;
    30.     }
    32.     public static void main(String[] args) {
    33.         int[] pre = {1,2,4,7,3,5,6,8};
    34.         int[] in = {4,7,2,1,5,3,8,6};
    35.         BinaryTree.printPostTree(reConstructBinaryTree(pre,in));
    36.     }
    37. }
    39. class BinaryTree {
    40.     public BinaryTree left;
    41.     public BinaryTree right;
    42.     public int value;
    44.     public BinaryTree(int value) {
    45.         this(null, null, value);
    46.     }
    48.     public BinaryTree(BinaryTree left, BinaryTree right, int value) {
    49.         this.left = left;
    50.         this.right = right;
    51.         this.value = value;
    52.     }
    54.     public void insertLeft(BinaryTree currentNode, int value) {
    55.         if (currentNode == null) {
    56.             return;
    57.         }
    59.         BinaryTree newLeftNode = new BinaryTree(value);
    60.         if (currentNode.left != null) {
    61.             newLeftNode.left = currentNode.left;
    62.         }
    63.         currentNode.left = newLeftNode;
    64.     }
    66.     public void insertRight(BinaryTree currentNode, int value) {
    67.         if (currentNode == null) {
    68.             return;
    69.         }
    71.         BinaryTree newRightNode = new BinaryTree(value);
    72.         if (currentNode.right != null) {
    73.             newRightNode.right = currentNode.right;
    74.         }
    75.         currentNode.right = newRightNode;
    76.     }
    78.     //前序遍历二叉树
    79.     public static void printPreTree(BinaryTree currentNode) {
    80.         if (currentNode == null) {
    81.             return;
    82.         }
    83.         System.out.print(currentNode.value);
    84.         System.out.print("--");
    85.         if (currentNode.left != null) {
    86.             printPreTree(currentNode.left);
    87.         }
    88.         if (currentNode.right != null) {
    89.             printPreTree(currentNode.right);
    90.         }
    91.     }
    93.     //中序遍历二叉树
    94.     public static void printInTree(BinaryTree currentNode) {
    95.         if (currentNode == null) {
    96.             return;
    97.         }
    98.         if (currentNode.left != null) {
    99.             printInTree(currentNode.left);
    100.         }
    101.         System.out.print(currentNode.value);
    102.         System.out.print("--");
    103.         if (currentNode.right != null) {
    104.             printInTree(currentNode.right);
    105.         }
    106.     }
    108.     //后序遍历二叉树
    109.     public static void printPostTree(BinaryTree currentNode){
    110.         if(currentNode == null){
    111.             return;
    112.         }
    113.         if(currentNode.left != null){
    114.             printPostTree(currentNode.left);
    115.         }
    116.         if (currentNode.right != null){
    117.             printPostTree(currentNode.right);
    118.         }
    119.         System.out.print(currentNode.value);
    120.         System.out.print("--");
    121.     }
    122. }

    扩展：如果给出的是中序遍历和后序遍历呢（和上述过程差不多）
    前序遍历+后序遍历：不能确定二叉树，所以不能重建