题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

3 / \ 9 20 / \ 15 7

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

递归

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { HashMap<Integer,Integer> mapOfIndex = new HashMap<>(); // 把中序数组放进map中 便于寻找数字的index for(int i = 0; i < inorder.length; i++){ mapOfIndex.put(inorder[i], i); } return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1, mapOfIndex); } // p_left 和 p_right 是左右子树在pre order的开始和结尾范围 不包括根结点 // i_left 和 i_right 是左右子树在in order的开始和结尾范围 不包括根结点 public TreeNode build(int[] preorder, int p_left, int p_right, int[] inorder, int i_left, int i_right, HashMap<Integer,Integer> mapOfIndex){ // preorder为空 就结束循环 在preorder root的位置后面没有东西了 说明没了 if(p_left > p_right) return null; int rootVal = preorder[p_left]; TreeNode root = new TreeNode(rootVal); if(p_left == p_right) return root; // 找到该根结点在inorder里的index int rootIndex = mapOfIndex.get(rootVal); // 左子树的大小 用于计算后面左右子树 int sizeOfLeft = rootIndex - i_left; // 构建左右子树 root.left = build(preorder, p_left + 1, p_left + sizeOfLeft, inorder, i_left, rootIndex-1, mapOfIndex); root.right = build(preorder, p_left + sizeOfLeft + 1, p_right, inorder, rootIndex + 1, i_right, mapOfIndex); return root; } }

迭代 栈