剑指Offer：重建二叉树（Java实现）

原题:
点击此处
这道题真的折磨了好几次，都还是不会。

这次总结了几个关键点，希望下次再打的时候可以记住。

关键点：

1. 可以使用哈希表来记住中序遍历的值对应的索引，这样就不用每次都过一次循环了。
2. 前序遍历最重要的作用就是找到根节点罢了，所以递归的时候传入根节点的位置就可以了，不用考虑前序遍历的开始和结束
3. 中序遍历要记住开始和结束，但是无论哪种情况，递归结束的重点都是left > right
4. 不要把tree当做参数传到递归里面，会引发引用错乱，而应该想下面的代码直接在递归中写出树的左节点和树的右节点。

import java.util.*;
public class Solution {
    Map<Integer,Integer> hashMap = new HashMap<>();
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        //防止非法输入
        if(pre.length == 0 || in.length == 0){
            return null;
        }
        //用哈希表来记录索引
        for(int i = 0;i<in.length;i++){
            hashMap.put(in[i],i);
        }
        return build(pre,0,in,0,in.length-1);
    }
    
    public TreeNode build(int[] pre,int rootPoint,int[] in,int left,int right){
        //递归出口
        if(left > right){
            return null;
        }
        TreeNode tree = new TreeNode(pre[rootPoint]);
        //得到根的索引
        int i = hashMap.get(pre[rootPoint]);
        tree.left = build(pre,rootPoint+1,in,left,i-1);
        tree.right = build(pre,rootPoint+1+i-left,in,i+1,right);
        return tree;
    }
}

本文地址：https://blog.csdn.net/qq_26558047/article/details/110804180