1，题目：
2，思路：
递归解析：
1.递推参数： 前序遍历中根节点的索引pre_root、中序遍历左边界in_left、中序遍历右边界in_right。2.终止条件： 当 in_left > in_right ，子树中序遍历为空，说明已经越过叶子节点，此时返回 null 。3.递推工作：4.建立根节点root： 值为前序遍历中索引为pre_root的节点值。5.搜索根节点root在中序遍历的索引i： 为了提升搜索效率，本题解使用哈希表 dic 预存储中序遍历的值与索引的映射关系，每次搜索的时间复杂度为 O(1)。6.构建根节点root的左子树和右子树： 通过调用 recur() 方法开启下一层递归。7.左子树： 根节点索引为 pre_root + 1 ，中序遍历的左右边界分别为 in_left 和 i - 1。8.右子树： 根节点索引为 i - in_left + pre_root + 1（即：根节点索引 + 左子树长度 + 1），中序遍历的左右边界分别为 i + 1 和 in_right。9.返回值： 返回 root，含义是当前递归层级建立的根节点 root 为上一递归层级的根节点的左或右子节点。下面是对应的图解：
方法二：迭代法：
1.使用前序遍历的第一个元素创建根节点。 2.创建一个栈，将根节点压入栈内。 3.初始化中序遍历下标为 0。 4.遍历前序遍历的每个元素，判断其上一个元素（即栈顶元素）是否等于中序遍历下标指向的元素。 5.若上一个元素不等于中序遍历下标指向的元素，则将当前元素作为其上一个元素的左子节点，并将当前元素压入栈内。 6.若上一个元素等于中序遍历下标指向的元素，则从栈内弹出一个元素，同时令中序遍历下标指向下一个元素，之后继续判断栈顶元素是否等于中序遍历下标指向的元素，若相等则重复该操作，直至栈为空或者元素不相等。然后令当前元素为最后一个想等元素的右节点。 7.遍历结束，返回根节点。
3，代码：
递归法：
class Solution { /* 递归解析： 1.递推参数： 前序遍历中根节点的索引pre_root、中序遍历左边界in_left、中序遍历右边界in_right。 2.终止条件： 当 in_left > in_right ，子树中序遍历为空，说明已经越过叶子节点，此时返回 null 。 3.递推工作： 4.建立根节点root： 值为前序遍历中索引为pre_root的节点值。 5.搜索根节点root在中序遍历的索引i： 为了提升搜索效率，本题解使用哈希表 dic 预存储中序遍历的值与索引的映射关系，每次搜索的时间复杂度为 O(1)。 6.构建根节点root的左子树和右子树： 通过调用 recur() 方法开启下一层递归。 7.左子树： 根节点索引为 pre_root + 1 ，中序遍历的左右边界分别为 in_left 和 i - 1。 8.右子树： 根节点索引为 i - in_left + pre_root + 1（即：根节点索引 + 左子树长度 + 1），中序遍历的左右边界分别为 i + 1 和 in_right。 9.返回值： 返回 root，含义是当前递归层级建立的根节点 root 为上一递归层级的根节点的左或右子节点。 */ HashMap<Integer, Integer> dic = new HashMap<>(); int[] po; public TreeNode buildTree(int[] preorder, int[] inorder) { po = preorder; for(int i = 0; i < inorder.length; i++) dic.put(inorder[i], i); return recur(0, 0, inorder.length - 1); } TreeNode recur(int pre_root, int in_left, int in_right) { if(in_left > in_right) return null; TreeNode root = new TreeNode(po[pre_root]);//建立根节点root： 值为前序遍历中索引为pre_root的节点值。 int i = dic.get(po[pre_root]); root.left = recur(pre_root + 1, in_left, i - 1);//左子树： 根节点索引为 pre_root + 1 ，中序遍历的左右边界分别为 in_left 和 i - 1。 root.right = recur(pre_root + i - in_left + 1, i + 1, in_right);//右子树： 根节点索引为 i - in_left + pre_root + 1（即：根节点索引 + 左子树长度 + 1），中序遍历的左右边界分别为 i + 1 和 in_right。 return root; } }方法二：迭代法：
class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { //迭代 /* 1.使用前序遍历的第一个元素创建根节点。 2.创建一个栈，将根节点压入栈内。 3.初始化中序遍历下标为 0。 4.遍历前序遍历的每个元素，判断其上一个元素（即栈顶元素）是否等于中序遍历下标指向的元素。 5.若上一个元素不等于中序遍历下标指向的元素，则将当前元素作为其上一个元素的左子节点，并将当前元素压入栈内。 6.若上一个元素等于中序遍历下标指向的元素，则从栈内弹出一个元素，同时令中序遍历下标指向下一个元素，之后继续判断栈顶元素是否等于中序遍历下标指向的元素，若相等则重复该操作，直至栈为空或者元素不相等。然后令当前元素为最后一个想等元素的右节点。 7.遍历结束，返回根节点。 */ if (preorder == null || preorder.length == 0) { return null; } TreeNode root = new TreeNode(preorder[0]); int length = preorder.length; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); int inorderIndex = 0; for (int i = 1; i < length; i++) {//遍历前序遍历的每个元素，判断其上一个元素（即栈顶元素）是否等于中序遍历下标指向的元素。 int preorderVal = preorder[i]; TreeNode node = stack.peek(); if (node.val != inorder[inorderIndex]) { node.left = new TreeNode(preorderVal); stack.push(node.left); } else { while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) { node = stack.pop(); inorderIndex++; } node.right = new TreeNode(preorderVal); stack.push(node.right); } } return root; } }