思路 首先二叉搜索树需要中序遍历，但如果是中序遍历，计算前面节点依赖于后面节点的结果。所以将中序遍历倒过来即可。 二叉树的遍历不止3种，可以自行调整。 题目 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.va…

思路 利用二叉搜索树的特征：中序遍历后是个递增的序列，很容易就AC了。 这样的时间复杂度是O(n)，如果节点已经存储了序号，就可以像查找值一样O(logN)。 叶节点也满足二叉搜索树 题目 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。   示例 1： 输入：root = …

思路 使用前序遍历序列化，遍历的元素往链表末尾添加，根节点先添加，再左子节点，右子节点。所以根节点在链表头部，有了这个信息就好做了，毕竟二叉树的遍历就是找到根节点+做点啥+递归。 使用前序遍历反序列化，需要先得出根节点，在链表的头部，将其抛出。再找出左子节点，还是链表的头部，将其抛出，继续寻找左子节点的左子节点。。。 中序遍历无法反序列化，因为根节…

思路 问题一：如果遍历比较 遍历所有节点，然后两两比较。时间复杂度O(n)。一看性能就不行。 利用set来判断是否重复。不过有重复多次的情况，但只需返回一个重复节点，所以还需要记录count，使用map即可。 问题二：如何判断两个节点结构相同 通过递归，同时遍历两个节点。因为一个节点需要和多次比较，所以同一个节点需要遍历多次，性能差。 序列化二叉树…

实战代理模式，模拟Mybatis 在使用mybatis操作数据库时，我们只需要定义一个接口，然后在xml里编写对应的sql，就能查询数据。其原理是Mybatis通过@mypperscan指定扫描的mapper接口路径，对mapper接口进行动态代理，生成的代理类通过解析xml得到对应sql，最终开发人员只需要调用接口就能执行sql了。 今天我们来实…

Proxy Design Pattern 作用 对原有功能进行增强，注意这里的增强是增加额外的功能，和原有功能无关。 使用场景 业务系统中增加非功能性需求，比如：监控、统计、鉴权、限流、事务、幂等、日志等。 还可以实现接口缓存，通过请求参数决定使用缓存还是实时查询。 实现方式 静态代理 代理接口 代理类和被代理类实现同样的接口，通过组合的形式，进行…

Visitor pattern 因为它难理解、难实现，应用它会导致代码的可读性、可维护性变差，所以，访问者模式在实际的软件开发中很少被用到，在没有特别必要的情况下，建议你不要使用访问者模式。 ——设计模式之美 前言 这个模式侧重代码实现，主要是解决分离业务代码，抽取能力带来的问题。 示例V1 模拟读取不同格式的文件。 ResourceFileV1：…

Memento Design Pattern 定义 在不违背封装原则的情况下，捕获一个对象的内部状态，并在该对象之外保存这个状态，以便以后恢复对象为先前的状态。 应用场景 防丢失、撤销、恢复。可以理解为备份操作，只不过是从代码设计的层面来考虑的。 示例 来自极客时间 输入单词，支持撤销操作。 用户输入文本时，程序将其追加存储在内存文本中；用户输入“…

思路 简单的方法是遍历一边链表，存入数组，再从首尾往中间判断是否相等。但是题目说了，进阶的解法是空间复杂度为O(1)，首先排除递归反转链表，倒是可以利用迭代来反转链表。在优化下，不用反转整条链表来比较，只需反转半条即可。 一次就AC了，爽 题目 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 …

State Pattern 有限状态机 简称状态机， 由三部分组成：状态、事件、动作。事件触发状态转移，执行动作（非必须）。 状态机实现方式一：分支逻辑法 就是各种if else，switch case。判断不同的状态，遇到不同的事件，执行不同的操作，例如改变状态，执行动作。适用于简单的场景，毕竟不要过度设计。 状态机实现方式二：查表法 状态机有两…