剑指 Offer 07. 重建二叉树 java递归

题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof

这道题显然遍历还原二叉树，一般递归的思路会比较简单，对应左右子树的返回即可解决，但同时有一个问题就是栈空间的存储空间需要比较大。对应非递归思路上难实现，但空间压缩以及时间复杂度O(N)。
对于递归套路：

• 确定终止条件
• 头节点的确定 线序遍历第一个数
• 右子树对应的数据
• 左子树对应的数据
• 返回头节点

递归过程就是上面这样。而要在中序遍历中确定根节点就可以利用哈希表来实现。

DM:

public static HashMap map;
    public TreeNode buildTree(int []preorder, int[] inorder) {
        map=new HashMap<>();
         for(int i=0;ip_r){
            return null;
        }
        int p_f=p_l;
        int i_m=map.get(preorder[p_f]);
        int dis=i_m-i_l;
        TreeNode root=new TreeNode(preorder[p_f]);
        root.left=fun(preorder,inorder,p_f+1,p_f+dis,i_l,i_m-1);
        root.right=fun(preorder,inorder,p_f+dis+1,p_r,i_m+1,i_r);
        return root;
    }