给定两个整数数组preorder 和 inorder，其中preorder 是二叉树的先序遍历， inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder和inorder均 无重复 元素
inorder均出现在preorder
preorder保证 为二叉树的前序遍历序列
inorder保证 为二叉树的中序遍历序列
来源：力扣（LeetCode）
链接：/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
感谢windliang大佬的详细解法，传送门详细通俗的思路分析，多解法
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {//return buildTreeI(preorder, inorder);return buildTreeII(preorder, inorder);}//方法二：迭代，时间和空间复杂度O(N)//定义栈保存遍历过的节点，定义index指向中序遍历位置private TreeNode buildTreeII(int[] preorder, int[] inorder) {if (preorder == null || inorder == null) {return null;}TreeNode root = new TreeNode(preorder[0]);Stack<TreeNode> stack = new Stack<>();stack.push(root);int index = 0;for (int i = 1; i < preorder.length; i++) {int preorderVal = preorder[i];//栈顶节点TreeNode node = stack.peek();//栈顶节点不等于中序遍历数组值，当前节点作为栈顶节点的左子树if (node.val != inorder[index]) {node.left = new TreeNode(preorderVal);stack.push(node.left);} else {//栈顶节点等于中序遍历数组值，说明左子树遍历结束了，开始遍历右子树while (!stack.isEmpty() && stack.peek().val == inorder[index]) {//不断出栈，找到最后一次相等的位置，并把当前节点作为它的右子树node = stack.pop();index++;}node.right = new TreeNode(preorderVal);stack.push(node.right);}}return root;}//方法一：递归，时间和空间复杂度O(N)private TreeNode buildTreeI(int[] preorder, int[] inorder) {if (preorder == null || inorder == null) {return null;}Map<Integer, Integer> map = new HashMap<>();//定义map，记录中序遍历元素与索引对应关系for (int i = 0; i < inorder.length; i++) {map.put(inorder[i], i);}return buildTree(preorder, 0, preorder.length - 1, map, 0, inorder.length - 1);}private TreeNode buildTree(int[] preorder, int preStart, int preEnd, Map<Integer, Integer> map, int inStart, int inEnd) {if (preStart > preEnd) {return null;}//根节点为前序遍历第一位int rootVal = preorder[preStart];//根节点在中序遍历的位置int index = map.get(rootVal);//左子树数组长度等于根节点位置减去中序遍历首位置int leftSize = index - inStart;TreeNode root = new TreeNode(rootVal);//递归构建左右子树root.left = buildTree(preorder, preStart + 1, preStart + leftSize, map, inStart, index - 1);root.right = buildTree(preorder, preStart + leftSize + 1, preEnd, map, index + 1, inEnd);return root;}}
如果觉得《Leetcode刷题105. 从前序与中序遍历序列构造二叉树》对你有帮助，请点赞、收藏，并留下你的观点哦！
