目录

昨日总结

今日计划

算法——从中序与后序遍历序列构造二叉树

算法——最大二叉树

昨日八股答案 

今日八股

---

昨日总结

• 小林coding--Spring面试篇(3/7)
• 码随想录——从中序与后序遍历序列构造二叉树  ,最大二叉树

今日计划

• JVM底层原理学习，学习mysql进阶篇，学习函数式编程
• cv（停滞中）
• 小林coding--Spring面试篇(4/7)
• 码随想录——合并二叉树，二叉搜索树中的搜索，验证二叉搜索树

算法——从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 :

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //设置全局的map，用于标记两个遍历顺序的相同值所在的位置
    Map<Integer, Integer> map;  
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        //用中序遍历记录值对应数组的位置
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        //递归建立树
        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  
    }
    //因为构造树两端，需要知道开始和截止的数组位置。
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
       //当有一方遍历顺序完成时，返回
        if (inBegin >= inEnd || postBegin >= postEnd) {  
            return null;
        }
        //从后续遍历中确定根节点
        int rootIndex = map.get(postorder[postEnd - 1]); 
        //逐步构建根节点成树
        TreeNode root = new TreeNode(inorder[rootIndex]);  
        int lenOfLeft = rootIndex - inBegin;  
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);

        return root;
    }
}

算法——最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例 ：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dg(nums, 0 , nums.length);
    }

    public TreeNode dg(int[] nums, int begin , int end) {
        if(begin >= end)
        return null;
        if(end - begin == 1)
        return new TreeNode(nums[begin]);
        int maxindex = begin;
        int max = nums[begin];
        for (int i = begin + 1; i < end; i++) {
            if(nums[i] > max) {
                max = nums[i];
                maxindex = i;
            }
        }
        TreeNode root = new TreeNode(max);
        root.left = dg(nums, begin , maxindex);
        root.right = dg(nums, maxindex + 1 , end);
        return root;
    }
    
}

昨日八股答案 

• Spring三级缓存的数据结构是什么

一级缓存：Map类型的缓存，存储的是已经完全初始化好的bean，键是bean的名称，值是bean的实例

二级缓存：Map类型的缓存，存储的是早期的bean引用，已经实例化但还未完全初始化的bean，这些bean已经被实例化，但是没有进行属性注入等操作

三级缓存：Map类型的缓存，存储的是objectFactor对象，对象可以生成早期的bean引用。当一个bean正在创建过程中，如果它被其他bean依赖，那么这个正在创建的bean就会通过这个ObjectFactory来创建一个早期引用，从而解决循环依赖的问题。

• Spring常用的注解

1. Autowired：自动装备Bean，当Spring容器存在与要注入的属性类型匹配的bean时，他会自动将bena注入到属性中。
2. Component：标记一个类作为Spring的Bean，将类实例化为一个bean，将其添加到Spring容器中。
3. Configuration：标记一个类作为Spring的配置类。配置类可以包括@bean注解，用于定义和配置bean
4. Bean: 标记一个方法作为Spring的bean工厂方法。当一个方法被@Bean注解标记时，Spring还会将该方法的返回值作为一个bean，将其添加到Spring容器中，如果自定义配置，经常用到这个注解。
5. @Service：标记一个类作为服务层的组件。是component注解的特例，用于标记服务层的bean
6. Repository：标记一个类作为数据访问层的组件。也是component的注解的特例，标记数据访问层的bean
7. Controller：标记一个类作为控制层的组件，也是component注解的特例，标记控制层的bean

• Spring的事务在什么情况下会失效

1. 如果一个事务方法中发生了未捕获的异常，并且异常未被处理，事务会失效，所有数据库操作会回滚
2. Spring对非授检异常（通常由程序逻辑错误引起的，指在程序编译阶段不需要强制处理的异常）进行回滚操作
3. 如果在多个事务之间存在事务嵌套，且事务传播属性配置不正确可能会导致事务失效
4. 如果一个事务方法内部调用另一个方法，而这个被调用的方法没有标记Transactional注解，这种情况下外层事务可能会失效
5. 如果Transactional注解标记在私有方法或非public方法上，事务也会失效

今日八股

• Spring bean的作用域有哪些

• 在Spring中，在bean加载/销毁前后，如果想实现某些逻辑，可以怎么做

• Spring MVC的理解以及工作流程
• Spring boot的理解以及优点