一、题目描述
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
限制：
0 <= 节点个数 <= 5000
二、思路讲解
根据二叉树的遍历知识我们可以知道，前序遍历的第一个节点为根节点；中序遍历中，根节点左边所有的节点在它的左子树中，右边所有的节点在它的右子树中。也就是说，前序遍历数组和后序遍历数组可以分成这样的结构：
前序遍历数组： | 根节点 | 左子树 | 右子树 |
中序遍历数组： | 左子树 | 根节点 | 右子树 |
前序遍历中，根节点右边的节点就是左子树的根节点，而我们可以在中序遍历中找到左子树的长度left_len，那么，在前序遍历数组中距离根节点left_len的节点就是右子树的根节点。
我们就可以根据这个思路遍历树中所有的节点。
三、Java代码实现
/** * 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) { return fun(0, inorder.length-1, 0, preorder, inorder); } /** left: 左子树在inorder上的左边界 right： 右子树的inorder上的右边界 index： 当前节点在inorder上的索引 */ public static TreeNode fun(int left, int right, int index, int[] preorder, int[] inorder){ //越过了叶子节点 if(left>right){ return null; } //构造树 TreeNode root = new TreeNode(preorder[index]); int i; //在中序数组上找到当前节点。当前节点左边为左子树，右边为右子树 for(i=0; i<inorder.length; i++){ if(inorder[i] == preorder[index]){ break; } } //构建当前节点的左子树 root.left = fun(left, i-1, index+1, preorder, inorder); //构建当前节点的右子树 root.right = fun(i+1, right, index+i-left+1, preorder, inorder); return root; } }
四、代码优化
1、用HashMap来保存中序数组
因为每次遍历时都要用一个循环去中序数组中找当前节点，那么我们用一个HashMap来保存中序数组中的所有节点，这样再找时，时间复杂度为O(1)。虽然会提升一点空间复杂度，但是大大降低了时间复杂度。
2、将前序遍历数组拿到方法外面
这样就不需要每次递归的时候都传入了，也能降低空间复杂度。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private static int[] preorder; //用来保存inorder，使查找的速度加快 private static HashMap<Integer, Integer> map = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; for(int i=0; i<inorder.length; i++){ map.put(inorder[i], i); } return fun(0, inorder.length-1, 0); } /** left: 左子树在inorder上的左边界 right： 右子树的inorder上的右边界 index： 当前节点在inorder上的索引 */ public static TreeNode fun(int left, int right, int index){ //越过了叶子节点 if(left>right){ return null; } //构造树 TreeNode root = new TreeNode(preorder[index]); //在中序数组上找到当前节点。当前节点左边为左子树，右边为右子树 int i = map.get(preorder[index]); //构建当前节点的左子树 root.left = fun(left, i-1, index+1); //构建当前节点的右子树 root.right = fun(i+1, right, index+i-left+1); return root; } }
