先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。
    中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。
    后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。

    若知道先序遍历结果，那么第一个元素即是根节点
    若知道后序遍历结果，那么最后一个元素即是根节点
    中序遍历序列可以根据根节点位置可以得到左子树的中序遍历序列和右子树的中序遍历序列
    前序遍历序列可以根据根节点和左子树的中序遍历序列元素数量得到左子树的前序遍历序列和右子树的前序遍历序列

    比如二叉树：

    1.       3
    2.     /   \
    3.   9       20
    4.  / \     / \
    5. 6   8   15  7

    前序遍历序列：[3, 9, 6, 8, 20, 15, 7]
    中序遍历序列：[6, 9, 8, 3, 15, 20, 7]
    那么根节点就是前序遍历的第一个元素：3
    左子树的中序遍历序列就是中序遍历序列根节点元素左侧部分：[6, 9, 8]
    右子树的中序遍历序列就是中序遍历序列根节点元素右侧部分：[15, 20, 7]
    左子树的前序遍历序列就是前序遍历序列根节点元素右侧3个元素：[9, 6, 8]
    右子树的前序遍历序列就是前序遍历序列中左子树的前序遍历序列后边部分：[20, 15, 7]

    即
    前序遍历序列：[根节点，[左子树的前序遍历序列]，[右子树的前序遍历序列]]
    中序遍历序列：[[左子树的中序遍历序列]，根节点，[右子树的中序遍历序列]]

    算法框架

    1. public TreeNode buildTree(int[] preorder, int[] inorder) {
    2.     // 找到根节点
    3.     int rootValue = ?;
    4.     // 找到根节点在中序遍历序列中的索引位置
    5.     int rootIndex = ?;
    6.     // 构建根节点
    7.     TreeNode root = new TreeNode(rootValue);
    8.     // 得到构建左子树的前序遍历序列
    9.     int[] leftPreorder = ?;
    10.     // 得到构建左子树的中序遍历序列
    11.     int[] leftInorder = ?;
    12.     // 构建左子树
    13.     root.left = buildTree(leftPreorder, leftInorder);
    14.     // 得到构建右子树的前序遍历序列
    15.     int[] rightPreorder = ?;
    16.     // 得到构建右子树的中序遍历序列
    17.     int[] rightInorder = ?;
    18.     // 构建右子树
    19.     root.right = buildTree(rightPreorder, rightInorder);
    20.     return root;
    21. }

    根节点就是前序遍历序列第一个元素：

    1. int rootValue = preorder[0];

    找到根节点在中序遍历序列中的索引位置：

    1. int rootIndex = -1;
    2. for (int i = 0; i < inorder.length; i++) {
    3.     if (inorder[i] == rootValue) {
    4.         rootIndex = i;
    5.     }
    6. }

    若要构建左子树，则需要先得到左子树的前序遍历序列和中序遍历序列
    若要构建右子树，则需要先得到右子树的前序遍历序列和中序遍历序列

    初始化四个数组，分别代表左子树的前序遍历序列和中序遍历序列以及右子树的前序遍历序列和中序遍历序列

    1. int[] leftProrder = new int[];
    2. int[] leftInorder = new int[];
    3. int[] rightProrder = new int[];
    4. int[] rightInorder = new int[];

    可是数组初始化需要确定数组长度，即元素个数
    左子树的元素个数即中序遍历序列根节点左侧的元素个数，值等于 根节点的索引值
    右子树的元素个数即中序遍历序列根节点右侧的元素个数，值等于 中序遍历序列的元素数量 - 左子树元素数量 - 根节点 ，也等于 中序遍历序列最大索引值 - 根节点索引值

    1. // 左子树节点数量
    2. int leftSize = rootIndex;
    3. // 右子树节点数量
    4. int rightSize = inorder.length - 1 - rootIndex;

    左子树的中序遍历序列就是中序遍历序列根节点元素左侧部分：

    1. for (int i = 0, j = 0; i < leftSize; i++, j++) {
    2.     // 从 inorder 第 0 个元素开始，取 leftSize 个元素
    3.     leftInorder[j] = inorder[i];
    4. }

    右子树的中序遍历序列就是中序遍历序列根节点元素右侧部分：

    1. for (int i = rootIndex + 1, j = 0; i < inorder.length; i++, j++) {
    2.     // 从 inorder 第 rootIndex + 1 元素开始，直至结束
    3.     rightInorder[j] = inorder[i];
    4. }

    左子树的前序遍历序列就是前序遍历序列根节点元素右侧左子树元素总数数量的N个元素：

    1.  for (int i = 1, j = 0; i <= leftSize; i++, j++) {
    2.     // 从 preorder 第 2 个元素开始，取 leftSize 个元素
    3.     leftPreorder[j] = preorder[i];
    4. }

    右子树的前序遍历序列就是前序遍历序列中左子树的前序遍历序列后边部分：

    1. for (int i = rootIndex + 1, j = 0; i < preorder.length; i++, j++) {
    2.     // 从 preorder 第 rootIndex + 1 元素开始，直至结束
    3.     rightPreorder[j] = preorder[i];
    4. }

    算法框架

    1. public TreeNode buildTree(int[] preorder, int[] inorder) {
    2.     // 找到根节点
    3.     int rootValue = preorder[0];;
    4.     // 找到根节点在中序遍历序列中的索引位置
    5.     int rootIndex = -1;
    6.     for (int i = 0; i < inorder.length; i++) {
    7.         if (inorder[i] == rootValue) {
    8.             rootIndex = i;
    9.         }
    10.     }
    11.     // 构建根节点
    12.     TreeNode root = new TreeNode(rootValue);
    13.     // 计算左子树节点数量
    14.     int leftSize = rootIndex;
    15.     // 计算右子树节点数量
    16.     int rightSize = inorder.length - 1 - rootIndex;
    17.     // 得到构建左子树的前序遍历序列
    18.     int[] leftPreorder = new int[leftSize];
    19.     for (int i = 1, j = 0; i <= leftSize; i++, j++) {
    20.         // 从 preorder 第 2 个元素开始，取 leftSize 个元素
    21.         leftPreorder[j] = preorder[i];
    22.     }
    23.     // 得到构建左子树的中序遍历序列
    24.     int[] leftInorder = new int[leftSize];
    25.     for (int i = 0, j = 0; i < leftSize; i++, j++) {
    26.         // 从 inorder 第 0 个元素开始，取 leftSize 个元素
    27.         leftInorder[j] = inorder[i];
    28.     }
    29.     // 构建左子树
    30.     root.left = buildTree(leftPreorder, leftInorder);
    31.     // 得到构建右子树的前序遍历序列
    32.     int[] rightPreorder = new int[rightSize];
    33.     for (int i = rootIndex + 1, j = 0; i < preorder.length; i++, j++) {
    34.         // 从 preorder 第 rootIndex + 1 元素开始，直至结束
    35.         rightPreorder[j] = preorder[i];
    36.     }
    37.     // 得到构建右子树的中序遍历序列
    38.     int[] rightInorder = new int[rightSize];
    39.     for (int i = rootIndex + 1, j = 0; i < inorder.length; i++, j++) {
    40.         // 从 inorder 第 rootIndex + 1 元素开始，直至结束
    41.         rightInorder[j] = inorder[i];
    42.     }
    43.     // 构建右子树
    44.     root.right = buildTree(rightPreorder, rightInorder);
    45.     return root;
    46. }

    考虑边界条件：
    1）preorder 或者 inorder 为空，则直接返回 null
    2）preorder 和 inorder 都只有一个节点，则直接返回根节点即可

    1. public TreeNode buildTree(int[] preorder, int[] inorder) {
    2.     if (preorder == null || inorder == null) {
    3.         return null;
    4.     }
    5.     if (preorder.length == 1 && inorder.length == 1) {
    6.         return new TreeNode(preorder[0]);
    7.     }
    8.     // 找到根节点
    9.     int rootValue = preorder[0];;
    10.     // 找到根节点在中序遍历序列中的索引位置
    11.     int rootIndex = -1;
    12.     for (int i = 0; i < inorder.length; i++) {
    13.         if (inorder[i] == rootValue) {
    14.             rootIndex = i;
    15.         }
    16.     }
    17.     // 构建根节点
    18.     TreeNode root = new TreeNode(rootValue);
    19.     // 计算左子树节点数量
    20.     int leftSize = rootIndex;
    21.     // 计算右子树节点数量
    22.     int rightSize = inorder.length - 1 - rootIndex;
    23.     // 得到构建左子树的前序遍历序列
    24.     int[] leftPreorder = new int[leftSize];
    25.     for (int i = 1, j = 0; i <= leftSize; i++, j++) {
    26.         // 从 preorder 第 2 个元素开始，取 leftSize 个元素
    27.         leftPreorder[j] = preorder[i];
    28.     }
    29.     // 得到构建左子树的中序遍历序列
    30.     int[] leftInorder = new int[leftSize];
    31.     for (int i = 0, j = 0; i < leftSize; i++, j++) {
    32.         // 从 inorder 第 0 个元素开始，取 leftSize 个元素
    33.         leftInorder[j] = inorder[i];
    34.     }
    35.     // 构建左子树
    36.     root.left = buildTree(leftPreorder, leftInorder);
    37.     // 得到构建右子树的前序遍历序列
    38.     int[] rightPreorder = new int[rightSize];
    39.     for (int i = rootIndex + 1, j = 0; i < preorder.length; i++, j++) {
    40.         // 从 preorder 第 rootIndex + 1 元素开始，直至结束
    41.         rightPreorder[j] = preorder[i];
    42.     }
    43.     // 得到构建右子树的中序遍历序列
    44.     int[] rightInorder = new int[rightSize];
    45.     for (int i = rootIndex + 1, j = 0; i < inorder.length; i++, j++) {
    46.         // 从 inorder 第 rootIndex + 1 元素开始，直至结束
    47.         rightInorder[j] = inorder[i];
    48.     }
    49.     // 构建右子树
    50.     root.right = buildTree(rightPreorder, rightInorder);
    51.     return root;
    52. }

    提交算法时发现未通过，有测试用例：preorder = [1, 2] inorder = [2, 1]，只有根节点和左子树

    1.     1
    2.   /   
    3. 2

    同理可能还存在只有根节点和右子树的情况：

    1. 1
    2.   \
    3.     2

    需要对左子树节点数量和右子树节点数量判空一下

    1. public TreeNode buildTree(int[] preorder, int[] inorder) {
    2.     if (preorder == null || inorder == null) {
    3.         return null;
    4.     }
    5.     if (preorder.length == 1 && inorder.length == 1) {
    6.         return new TreeNode(preorder[0]);
    7.     }
    8.     // 找到根节点
    9.     int rootValue = preorder[0];;
    10.     // 找到根节点在中序遍历序列中的索引位置
    11.     int rootIndex = -1;
    12.     for (int i = 0; i < inorder.length; i++) {
    13.         if (inorder[i] == rootValue) {
    14.             rootIndex = i;
    15.         }
    16.     }
    17.     // 构建根节点
    18.     TreeNode root = new TreeNode(rootValue);
    19.     // 计算左子树节点数量
    20.     int leftSize = rootIndex;
    21.     // 计算右子树节点数量
    22.     int rightSize = inorder.length - 1 - rootIndex;
    23.     if (leftSize > 0) {
    24.         // 得到构建左子树的前序遍历序列
    25.         int[] leftPreorder = new int[leftSize];
    26.         for (int i = 1, j = 0; i <= leftSize; i++, j++) {
    27.             // 从 preorder 第 2 个元素开始，取 leftSize 个元素
    28.             leftPreorder[j] = preorder[i];
    29.         }
    30.         // 得到构建左子树的中序遍历序列
    31.         int[] leftInorder = new int[leftSize];
    32.         for (int i = 0, j = 0; i < leftSize; i++, j++) {
    33.             // 从 inorder 第 0 个元素开始，取 leftSize 个元素
    34.             leftInorder[j] = inorder[i];
    35.         }
    36.         // 构建左子树
    37.         root.left = buildTree(leftPreorder, leftInorder);
    38.     }
    39.     if(rightSize > 0) {
    40.         // 得到构建右子树的前序遍历序列
    41.         int[] rightPreorder = new int[rightSize];
    42.         for (int i = rootIndex + 1, j = 0; i < preorder.length; i++, j++) {
    43.             // 从 preorder 第 rootIndex + 1 元素开始，直至结束
    44.             rightPreorder[j] = preorder[i];
    45.         }
    46.         // 得到构建右子树的中序遍历序列
    47.         int[] rightInorder = new int[rightSize];
    48.         for (int i = rootIndex + 1, j = 0; i < inorder.length; i++, j++) {
    49.             // 从 inorder 第 rootIndex + 1 元素开始，直至结束
    50.             rightInorder[j] = inorder[i];
    51.         }
    52.         // 构建右子树
    53.         root.right = buildTree(rightPreorder, rightInorder);
    54.     }
    55.     return root;
    56. }

    再次提交算法，测试通过

    实际上要构建一棵二叉树，只要知道如何构建根节点，如何构建左子树，如何构建右子树即可构建一棵二叉树
    而构建左子树和构建右子树和构建树是一样的，只需要递归调用构建树方法即可

    1. public TreeNode buildTree() {
    2.     // 找到根节点的值
    3.     int rootValue = ?;
    4.     // 找到根节点的索引
    5.     int rootIndex = ?;
    6.     // 构建根节点
    7.     TreeNode root = new TreeNode(rootValue);
    8.     // 构建左子树
    9.     root.left = buildTree();
    10.     // 构建右子树
    11.     root.right = buildTree();
    12.     return root;
    13. }

    105. 从前序与中序遍历序列构造二叉树 - 图1

    根据题意只要能确定前序遍历序列和中序遍历序列，即可最终构建出一棵二叉树
    只要知道前序遍历序列左侧起始索引和前序遍历序列右侧起始索引即可确定前序遍历序列
    只要知道中序遍历序列左侧起始索引和中序遍历序列右侧起始索引即可确定中序遍历序列

    1. public TreeNode buildTree(int[] preorder, int[] inorder, 
    2.                           int preLeftIndex, int preRightIndex, 
    3.                           int inLeftIndex, int inRightIndex) {
    4.     // 找到根节点的值
    5.     int rootValue = ?;
    6.     // 找到根节点的索引
    7.     int rootIndex = ?;
    8.     // 构建根节点
    9.     TreeNode root = new TreeNode(rootValue);
    10.     // 构建左子树
    11.     root.left = buildTree(preorder, inorder, ?, ?, ?, ?);
    12.     // 构建右子树
    13.     root.right = buildTree(preorder, inorder, ?, ?, ?, ?);
    14.     return root;
    15. }

    根节点的值即是初始前序遍历序列中指定的子前序遍历序列起始索引位置的元素值：int rootValue = preorder[preLeftIndex]
    左子树的前序遍历序列左侧起始索引位置即 preLeftIndex + 1
    左子树的前序遍历序列右侧结束索引位置即 preLeftIndex + 左子树节点数量 = preLeftIndex + rootIndex - inLeftIndex
    左子树的中序遍历序列左侧起始索引位置即 inLeftIndex
    左子树的中序遍历序列结束索引位置等于 inLeftIndex + 左子树节点数量 - 1 = inLeftIndex + rootIndex - inLeftIndex = rootIndex - 1
    右子树的前序遍历序列左侧起始索引位置等于 preLeftIndex + 左子树节点数量 + 1 = preLeftIndex + rootIndex - inLeftIndex + 1
    右子树的前序遍历序列右侧结束索引位置等于 preRightIndex
    右子树的中序遍历序列左侧起始索引位置等于 rootIndex + 1
    右子树的中序遍历序列右侧结束索引位置等于 inRightIndex

    1. public TreeNode buildTree(int[] preorder, int[] inorder,
    2.                               int preLeftIndex, int preRightIndex,
    3.                               int inLeftIndex, int inRightIndex,
    4.                               HashMap<Integer, Integer> valueIndexMap) {
    5.     if (preLeftIndex > preRightIndex) {
    6.         return null;
    7.     }
    8.     // 找到根节点的值
    9.     int rootValue = preorder[preLeftIndex];
    10.     // 找到根节点的索引
    11.     int rootIndex = valueIndexMap.get(rootValue);
    12.     // 左子树节点数量
    13.     int leftSize = rootIndex - inLeftIndex;
    14.     // 构建根节点
    15.     TreeNode root = new TreeNode(rootValue);
    16.     // 左子树前序遍历序列起始索引
    17.     int leftNextPreLeftIndex = preLeftIndex + 1;
    18.     // 左子树前序遍历序列结束索引
    19.     int leftNextPreRightIndex = preLeftIndex + leftSize;
    20.     // 左子树中序遍历序列起始索引
    21.     int leftNextInLeftIndex = inLeftIndex;
    22.     // 左子树中序遍历序列结束索引
    23.     int leftNextInRightIndex = inLeftIndex + leftSize;
    24.     // 构建左子树
    25.     root.left = buildTree(preorder, inorder,
    26.             leftNextPreLeftIndex, leftNextPreRightIndex,
    27.             leftNextInLeftIndex, leftNextInRightIndex,
    28.             valueIndexMap);
    29.     // 右子树前序遍历序列起始索引
    30.     int rightNextPreLeftIndex = preLeftIndex + leftSize + 1;
    31.     // 右子树前序遍历序列结束索引
    32.     int rightNextPreRightIndex = preRightIndex;
    33.     // 右子树中序遍历序列起始索引
    34.     int rightNextInLeftIndex = rootIndex + 1;
    35.     // 右子树中序遍历序列结束索引
    36.     int rightNextInRightIndex = inRightIndex;
    37.     // 构建右子树
    38.     root.right = buildTree(preorder, inorder,
    39.             rightNextPreLeftIndex, rightNextPreRightIndex,
    40.             rightNextInLeftIndex, rightNextInRightIndex,
    41.             valueIndexMap);
    42.     return root;
    43. }

    那怎么找到根节点的索引呢？在知道根节点的值的情况下，可以反向从原始中序遍历序列中定位到索引值，需要提前维护一下值和索引的映射关系

    1. public TreeNode buildTree(int[] preorder, int[] inorder) {
    2.     HashMap<Integer, Integer> valueIndexMap = new HashMap();
    3.     for(int i = 0; i < inorder.length; i++) {
    4.         valueIndexMap.put(inorder[i], i);
    5.     }
    6.     return buildTree(preorder, inorder, 
    7.                      0, preorder.length - 1, 
    8.                      0, inorder.length - 1, 
    9.                      valueIndexMap);
    10. }
    11. public TreeNode buildTree(int[] preorder, int[] inorder,
    12.                           int preLeftIndex, int preRightIndex,
    13.                           int inLeftIndex, int inRightIndex,
    14.                           HashMap<Integer, Integer> valueIndexMap) {
    15.     if (preLeftIndex > preRightIndex) {
    16.         return null;
    17.     }
    18.     // 找到根节点的值
    19.     int rootValue = preorder[preLeftIndex];
    20.     // 找到根节点的索引
    21.     int rootIndex = valueIndexMap.get(rootValue);
    22.     // 左子树节点数量
    23.     int leftSize = rootIndex - inLeftIndex;
    24.     // 构建根节点
    25.     TreeNode root = new TreeNode(rootValue);
    26.     // 左子树前序遍历序列起始索引
    27.     int leftNextPreLeftIndex = preLeftIndex + 1;
    28.     // 左子树前序遍历序列结束索引
    29.     int leftNextPreRightIndex = preLeftIndex + leftSize;
    30.     // 左子树中序遍历序列起始索引
    31.     int leftNextInLeftIndex = inLeftIndex;
    32.     // 左子树中序遍历序列结束索引
    33.     int leftNextInRightIndex = inLeftIndex + leftSize;
    34.     // 构建左子树
    35.     root.left = buildTree(preorder, inorder,
    36.             leftNextPreLeftIndex, leftNextPreRightIndex,
    37.             leftNextInLeftIndex, leftNextInRightIndex,
    38.             valueIndexMap);
    39.     // 右子树前序遍历序列起始索引
    40.     int rightNextPreLeftIndex = preLeftIndex + leftSize + 1;
    41.     // 右子树前序遍历序列结束索引
    42.     int rightNextPreRightIndex = preRightIndex;
    43.     // 右子树中序遍历序列起始索引
    44.     int rightNextInLeftIndex = rootIndex + 1;
    45.     // 右子树中序遍历序列结束索引
    46.     int rightNextInRightIndex = inRightIndex;
    47.     // 构建右子树
    48.     root.right = buildTree(preorder, inorder,
    49.             rightNextPreLeftIndex, rightNextPreRightIndex,
    50.             rightNextInLeftIndex, rightNextInRightIndex,
    51.             valueIndexMap);
    52.     return root;
    53. }