最佳实践

1、在重建二叉树过程中，对不同层的最右边节点收集 res大小与level比较，dfs根左右，那么i位置存的就是i层最左

import java.util.*;

public class Solution {
    private List<Integer> res;
    private Map<Integer, Integer> map;
    public int[] solve (int[] pre, int[] in) {
        res = new ArrayList<>();
        map = new HashMap<>();
        for(int i=0;i<in.length;i++){
            map.put(in[i], i);
        }
        dfs(pre,0, pre.length - 1, in, 0, in.length - 1, 0);
        int[] ans = new int[res.size()]; // 转成数组返回
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }

    private void dfs(int[] myPre, int start1, int end1, int[] myIn, int start2, int end2, int level) {
        if (start1 > end1) {
            return;
        }
        int rootVal = myPre[start1]; // 当前根结点
        //刚开始size =0 level0 加入根节点 下一层。。。lev=1 size=1 然后加入左节点了 到了右节点时候2<=1不成立
        if (res.size() <= level) {//最左 
            res.add(rootVal);
        }else {//如果有右
            res.set(level, rootVal);
        }
        int i = map.get(rootVal);
        dfs(myPre,start1 + 1, start1 + i - start2, myIn,start2, i - 1, level + 1);
        dfs(myPre,start1 + i - start2 + 1, end1,myIn, i + 1, end2, level + 1);
    }
}