缓存专题(三) Write Through（读穿 写穿）策略
发表更新中间件 / 缓存9 分钟读完 (大约1415个字)

缓存专题(三) Write Through（读穿 写穿）策略

这个策略的核心原则是用户只与缓存打交道，由缓存和数据库通信，写入或者读取数据。这就好比你在汇报工作的时候只对你的直接上级汇报，再由你的直接上级汇报给他的上级，你是不能越级汇报的。

Write Through 的策略是这样的：先查询要写入的数据在缓存中是否已经存在，如果已经存在，则更新缓存中的数据，并且由缓存组件同步更新到数据库中，如果缓存中数据不存在，我们把这种情况叫做“Write Miss（写失效）”。

一般来说，我们可以选择两种“Write Miss”方式：一个是“Write Allocate（按写分配）”，做法是写入缓存相应位置，再由缓存组件同步更新到数据库中；另一个是“No-write allocate（不按写分配）”，做法是不写入缓存中，而是直接更新到数据库中。

在 Write Through 策略中，我们一般选择“No-write allocate”方式，原因是无论采用哪种“Write Miss”方式，我们都需要同步将数据更新到数据库中，而“No-write allocate”方式相比“Write Allocate”还减少了一次缓存的写入，能够提升写入的性能。

Read Through 策略就简单一些，它的步骤是这样的：先查询缓存中数据是否存在，如果存在则直接返回，如果不存在，则由缓存组件负责从数据库中同步加载数据。

下面是 Read Through/Write Through 策略的示意图：

cache_through1.jpg

Read Through/Write Through 策略的特点是由缓存节点而非用户来和数据库打交道，在我们开发过程中相比 Cache Aside 策略要少见一些，原因是我们经常使用的分布式缓存组件，无论是 Memcached 还是 Redis 都不提供写入数据库，或者自动加载数据库中的数据的功能。而我们在使用本地缓存的时候可以考虑使用这种策略，比如说在上一节中提到的本地缓存 Guava Cache 中的 Loading Cache 就有 Read Through 策略的影子。

我们看到 Write Through 策略中写数据库是同步的，这对于性能来说会有比较大的影响，因为相比于写缓存，同步写数据库的延迟就要高很多了。那么我们可否异步地更新数据库？这就是我们接下来要提到的“Write Back”策略。

Write Back（写回）策略

这个策略的核心思想是在写入数据时只写入缓存，并且把缓存块儿标记为“脏”的。而脏块儿只有被再次使用时才会将其中的数据写入到后端存储中。

**需要注意的是，**在“Write Miss”的情况下，我们采用的是“Write Allocate”的方式，也就是在写入后端存储的同时要写入缓存，这样我们在之后的写请求中都只需要更新缓存即可，而无需更新后端存储了，我将 Write back 策略的示意图放在了下面：

cache_through3jpg.jpg

**发现了吗？**其实这种策略不能被应用到我们常用的数据库和缓存的场景中，它是计算机体系结构中的设计，比如我们在向磁盘中写数据时采用的就是这种策略。无论是操作系统层面的 Page Cache，还是日志的异步刷盘，亦或是消息队列中消息的异步写入磁盘，大多采用了这种策略。因为这个策略在性能上的优势毋庸置疑，它避免了直接写磁盘造成的随机写问题，毕竟写内存和写磁盘的随机 I/O 的延迟相差了几个数量级呢。

但因为缓存一般使用内存，而内存是非持久化的，所以一旦缓存机器掉电，就会造成原本缓存中的脏块儿数据丢失。所以你会发现系统在掉电之后，之前写入的文件会有部分丢失，就是因为 Page Cache 还没有来得及刷盘造成的。

**当然，你依然可以在一些场景下使用这个策略，在使用时，我想给你的落地建议是：**你在向低速设备写入数据的时候，可以在内存里先暂存一段时间的数据，甚至做一些统计汇总，然后定时地刷新到低速设备上。比如说，你在统计你的接口响应时间的时候，需要将每次请求的响应时间打印到日志中，然后监控系统收集日志后再做统计。但是如果每次请求都打印日志无疑会增加磁盘 I/O，那么不如把一段时间的响应时间暂存起来，经过简单的统计平均耗时，每个耗时区间的请求数量等等，然后定时地，批量地打印到日志中。

缓存专题(二) Cache Aside（旁路缓存）策略
发表更新中间件 / 缓存13 分钟读完 (大约1915个字)

缓存专题(二) Cache Aside（旁路缓存）策略

我们来考虑一种最简单的业务场景，比方说在你的电商系统中有一个用户表，表中只有 ID 和年龄两个字段，缓存中我们以 ID 为 Key 存储用户的年龄信息。那么当我们要把 ID 为 1 的用户的年龄从 19 变更为 20，要如何做呢？

**你可能会产生这样的思路：**先更新数据库中 ID 为 1 的记录，再更新缓存中 Key 为 1 的数据。

cache_aside1.jpg

**这个思路会造成缓存和数据库中的数据不一致。**比如，A 请求将数据库中 ID 为 1 的用户年龄从 19 变更为 20，与此同时，请求 B 也开始更新 ID 为 1 的用户数据，它把数据库中记录的年龄变更为 21，然后变更缓存中的用户年龄为 21。紧接着，A 请求开始更新缓存数据，它会把缓存中的年龄变更为 20。此时，数据库中用户年龄是 21，而缓存中的用户年龄却是 20。

cache_aside2.jpg

**为什么产生这个问题呢？**因为变更数据库和变更缓存是两个独立的操作，而我们并没有对操作做任何的并发控制。那么当两个线程并发更新它们的时候，就会因为写入顺序的不同造成数据的不一致。

另外，直接更新缓存还存在另外一个问题就是丢失更新。还是以我们的电商系统为例，假如电商系统中的账户表有三个字段：ID、户名和金额，这个时候缓存中存储的就不只是金额信息，而是完整的账户信息了。当更新缓存中账户金额时，你需要从缓存中查询完整的账户数据，把金额变更后再写入到缓存中。

这个过程中也会有并发的问题，比如说原有金额是 20，A 请求从缓存中读到数据，并且把金额加 1，变更成 21，在未写入缓存之前又有请求 B 也读到缓存的数据后把金额也加 1，也变更成 21，两个请求同时把金额写回缓存，这时缓存里面的金额是 21，但是我们实际上预期是金额数加 2，这也是一个比较大的问题。

**那我们要如何解决这个问题呢？**其实，我们可以在更新数据时不更新缓存，而是删除缓存中的数据，在读取数据时，发现缓存中没了数据之后，再从数据库中读取数据，更新到缓存中。

cache_aside3.jpg

这个策略就是我们使用缓存最常见的策略，Cache Aside 策略（也叫旁路缓存策略），这个策略数据以数据库中的数据为准，缓存中的数据是按需加载的。它可以分为读策略和写策略，其中读策略的步骤是：

  • 从缓存中读取数据；
  • 如果缓存命中，则直接返回数据；
  • 如果缓存不命中，则从数据库中查询数据；
  • 查询到数据后，将数据写入到缓存中，并且返回给用户。

写策略的步骤是：

  • 更新数据库中的记录；
  • 删除缓存记录。

你也许会问了，在写策略中，能否先删除缓存，后更新数据库呢？**答案是不行的，**因为这样也有可能出现缓存数据不一致的问题，我以用户表的场景为例解释一下。

假设某个用户的年龄是 20，请求 A 要更新用户年龄为 21，所以它会删除缓存中的内容。这时，另一个请求 B 要读取这个用户的年龄，它查询缓存发现未命中后，会从数据库中读取到年龄为 20，并且写入到缓存中，然后请求 A 继续更改数据库，将用户的年龄更新为 21，这就造成了缓存和数据库的不一致。

cache_aside4.jpg

那么像 Cache Aside 策略这样先更新数据库，后删除缓存就没有问题了吗？其实在理论上还是有缺陷的。假如某个用户数据在缓存中不存在，请求 A 读取数据时从数据库中查询到年龄为 20，在未写入缓存中时另一个请求 B 更新数据。它更新数据库中的年龄为 21，并且清空缓存。这时请求 A 把从数据库中读到的年龄为 20 的数据写入到缓存中，造成缓存和数据库数据不一致。

cache_aside5.jpg

不过这种问题出现的几率并不高，原因是缓存的写入通常远远快于数据库的写入，所以在实际中很难出现请求 B 已经更新了数据库并且清空了缓存，请求 A 才更新完缓存的情况。而一旦请求 A 早于请求 B 清空缓存之前更新了缓存，那么接下来的请求就会因为缓存为空而从数据库中重新加载数据，所以不会出现这种不一致的情况。

**Cache Aside 策略是我们日常开发中最经常使用的缓存策略，不过我们在使用时也要学会依情况而变。**比如说当新注册一个用户，按照这个更新策略，你要写数据库，然后清理缓存（当然缓存中没有数据给你清理）。可当我注册用户后立即读取用户信息，并且数据库主从分离时，会出现因为主从延迟所以读不到用户信息的情况。

而解决这个问题的办法恰恰是在插入新数据到数据库之后写入缓存，这样后续的读请求就会从缓存中读到数据了。并且因为是新注册的用户，所以不会出现并发更新用户信息的情况。

Cache Aside 存在的最大的问题是当写入比较频繁时，缓存中的数据会被频繁地清理，这样会对缓存的命中率有一些影响。如果你的业务对缓存命中率有严格的要求，那么可以考虑两种解决方案：

  1. 一种做法是在更新数据时也更新缓存，只是在更新缓存前先加一个分布式锁，因为这样在同一时间只允许一个线程更新缓存，就不会产生并发问题了。当然这么做对于写入的性能会有一些影响；

  2. 另一种做法同样也是在更新数据时更新缓存，只是给缓存加一个较短的过期时间，这样即使出现缓存不一致的情况，缓存的数据也会很快地过期，对业务的影响也是可以接受。

缓存专题(一) 缓存概述
发表更新中间件 / 缓存13 分钟读完 (大约1951个字)

缓存专题(一) 缓存概述

缓存分类

在我们日常开发中，常见的缓存主要就是静态缓存、分布式缓存和热点本地缓存这三种。

静态缓存在 Web 1.0 时期是非常著名的，它一般通过生成 Velocity 模板或者静态 HTML 文件来实现静态缓存，在 Nginx 上部署静态缓存可以减少对于后台应用服务器的压力。例如，我们在做一些内容管理系统的时候，后台会录入很多的文章，前台在网站上展示文章内容，就像新浪，网易这种门户网站一样。

当然，我们也可以把文章录入到数据库里面，然后前端展示的时候穿透查询数据库来获取数据，但是这样会对数据库造成很大的压力。即使我们使用分布式缓存来挡读请求，但是对于像日均 PV 几十亿的大型门户网站来说，基于成本考虑仍然是不划算的。

所以我们的解决思路是每篇文章在录入的时候渲染成静态页面，放置在所有的前端 Nginx 或者 Squid 等 Web 服务器上，这样用户在访问的时候会优先访问 Web 服务器上的静态页面，在对旧的文章执行一定的清理策略后，依然可以保证 99% 以上的缓存命中率。

这种缓存只能针对静态数据来缓存，对于动态请求就无能为力了。那么我们如何针对动态请求做缓存呢？这时你就需要分布式缓存了。

分布式缓存的大名可谓是如雷贯耳了，我们平时耳熟能详的 Memcached、Redis 就是分布式缓存的典型例子。它们性能强劲，通过一些分布式的方案组成集群可以突破单机的限制。所以在整体架构中，分布式缓存承担着非常重要的角色。

对于静态的资源的缓存你可以选择静态缓存，对于动态的请求你可以选择分布式缓存，那么什么时候要考虑热点本地缓存呢？

**答案是当我们遇到极端的热点数据查询的时候。**热点本地缓存主要部署在应用服务器的代码中，用于阻挡热点查询对于分布式缓存节点或者数据库的压力。

比如某一位明星在微博上有了热点话题，“吃瓜群众”会到他 (她) 的微博首页围观，这就会引发这个用户信息的热点查询。这些查询通常会命中某一个缓存节点或者某一个数据库分区，短时间内会形成极高的热点查询。

那么我们会在代码中使用一些本地缓存方案，如 HashMap，Guava Cache 或者是 Ehcache 等，它们和应用程序部署在同一个进程中，优势是不需要跨网络调度，速度极快，所以可以来阻挡短时间内的热点查询。来看个例子。

比方说你的垂直电商系统的首页有一些推荐的商品，这些商品信息是由编辑在后台录入和变更。你分析编辑录入新的商品或者变更某个商品的信息后，在页面的展示是允许有一些延迟的，比如说 30 秒的延迟，并且首页请求量最大，即使使用分布式缓存也很难抗住，所以你决定使用 Guava Cache 来将所有的推荐商品的信息缓存起来，并且设置每隔 30 秒重新从数据库中加载最新的所有商品。

首先，我们初始化 Guava 的 Loading Cache：

1
2
3
4
5
6
7
8
9
CacheBuilder<String, List<Product>> cacheBuilder = CacheBuilder.newBuilder().maximumSize(maxSize).recordStats(); // 设置缓存最大值
cacheBuilder = cacheBuilder.refreshAfterWrite(30, TimeUnit.Seconds); // 设置刷新间隔
 
LoadingCache<String, List<Product>> cache = cacheBuilder.build(new CacheLoader<String, List<Product>>() {
    @Override
    public List<Product> load(String k) throws Exception {
        return productService.loadAll(); // 获取所有商品
    }
});

这样，你在获取所有商品信息的时候可以调用 Loading Cache 的 get 方法，就可以优先从本地缓存中获取商品信息，如果本地缓存不存在，会使用 CacheLoader 中的逻辑从数据库中加载所有的商品。

由于本地缓存是部署在应用服务器中，而我们应用服务器通常会部署多台，当数据更新时，我们不能确定哪台服务器本地中了缓存，更新或者删除所有服务器的缓存不是一个好的选择，所以我们通常会等待缓存过期。因此，这种缓存的有效期很短，通常为分钟或者秒级别，以避免返回前端脏数据。

缓存的不足

通过了解上面的内容，你不难发现，缓存的主要作用是提升访问速度，从而能够抗住更高的并发。那么，缓存是不是能够解决一切问题？显然不是。事物都是具有两面性的，缓存也不例外，我们要了解它的优势的同时也需要了解它有哪些不足，从而扬长避短，将它的作用发挥到最大。

**首先，缓存比较适合于读多写少的业务场景，并且数据最好带有一定的热点属性。**这是因为缓存毕竟会受限于存储介质不可能缓存所有数据，那么当数据有热点属性的时候才能保证一定的缓存命中率。比如说类似微博、朋友圈这种 20% 的内容会占到 80% 的流量。所以，一旦当业务场景读少写多时或者没有明显热点时，比如在搜索的场景下，每个人搜索的词都会不同，没有明显的热点，那么这时缓存的作用就不明显了。

**其次，缓存会给整体系统带来复杂度，并且会有数据不一致的风险。**当更新数据库成功，更新缓存失败的场景下，缓存中就会存在脏数据。对于这种场景，我们可以考虑使用较短的过期时间或者手动清理的方式来解决。

**再次，之前提到缓存通常使用内存作为存储介质，但是内存并不是无限的。**因此，我们在使用缓存的时候要做数据存储量级的评估，对于可预见的需要消耗极大存储成本的数据，要慎用缓存方案。同时，缓存一定要设置过期时间，这样可以保证缓存中的会是热点数据。

**最后，缓存会给运维也带来一定的成本，**运维需要对缓存组件有一定的了解，在排查问题的时候也多了一个组件需要考虑在内。

虽然有这么多的不足，但是缓存对于性能的提升是毋庸置疑的，我们在做架构设计的时候也需要把它考虑在内，只是在做具体方案的时候需要对缓存的设计有更细致的思考，才能最大化的发挥缓存的优势。

LeetCode两个经典的排序算法
发表更新算法 / 排序3 分钟读完 (大约379个字)

LeetCode两个经典的排序算法

LeetCode两个经典的排序算法

这回是标题党， 记录下两个分而治之的排序算法（手写），分而治之的算法很容易改造成并行算法，肯定是未来的潮流， leetcode已通过， 两个算法都使用了原地(inplace)更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class Solution {
    public List<Integer> sortArray(int[] nums) {
        // merge(nums, 0, nums.length - 1);
        sort(nums, 0, nums.length - 1);
        return IntStream.of(nums).boxed().collect(Collectors.toList());
    }

	//-------------------归并排序-------------------//
    private void merge(int[] nums, int start, int end) {
        if (start >= end) return;
        int midIdx = start + (end - start) / 2;
        merge(nums, start, midIdx);
        merge(nums, midIdx+1, end);
        concat(nums, start, midIdx, end);
    }

    private void concat(int[] nums, int start, int midIdx, int end) {
        int[] tmp = new int[end - start + 1];
        int lp = start, rp = midIdx + 1, i = 0;

        while (lp <= midIdx && rp <= end) {
            tmp[i++] = nums[lp] < nums[rp] ? nums[lp++] : nums[rp++];
        }

        while (lp <= midIdx) {
            tmp[i++] = nums[lp++];
        }

        while (rp <= end) {
            tmp[i++] = nums[rp++];
        }

        System.arraycopy(tmp, 0, nums, start, tmp.length);
    }

    // -------------------  归并排序 链表 ---------------------//

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) return null;
            return merge(lists, 0 , lists.length - 1);
        }

        private ListNode merge(ListNode[] lists, int low, int high) {
            if (low == high) return lists[low];

            int mid = (high - low) / 2 + low;

            return mergeLists( merge(lists, low, mid), merge(lists, mid+1, high));
        }

        public ListNode mergeLists(ListNode node1, ListNode node2) {
            if (node1 == null) return node2;
            if (node2 == null) return node1;

            if (node1.val < node2.val) {
                node1.next = mergeLists(node1.next, node2);
                return node1;
                
            } else {
                node2.next = mergeLists(node1, node2.next);
                return node2;
            }
        }
    }
    
    //-------------------快速排序-------------------//

    private void sort(int[] nums, int start, int end) {
        if (start >= end) return;

        int bIdx = partition(nums, start, end);
        sort(nums, start, bIdx - 1);
        sort(nums, bIdx + 1, end);
    }

    private int partition(int[] nums, int start, int end) {
        int idx = start, base = nums[end];

        for (int i = start; i < end; i++) {
            if (nums[i] < base) {
                swap(nums, idx++, i);
            }
        }
        swap(nums, idx, end);
        return idx;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
季度总结 如何管理自我时间
发表更新工作 / 总结4 分钟读完 (大约615个字)

季度总结 如何管理自我时间

最近这个季度

最近比较忙，算了下自己可以利用的空闲时间，忙时一天可能只有1到3个小时空闲时间，甚至一天没有空余时间。一周大约只有30小时时间是可以利用的，如果算上玩手机时间只会更短，如果再把这些时间再浪费掉，可能最近半年的成长就只有一些项目经验而已了。所幸平常关注的博客和《软技能》这本书里有提及一些关于自我时间管理相关内容，我简单实践了2个月，分享下这方面的心得感悟。

计划和休息

《软技能》中作者是如何做计划的？

  • 季度计划 明确宏观目标，以及如何实现
  • 月计划 估算当月能完成多少工作量
  • 周计划 为每周安排必须完成的强制性任务
  • 日计划 排除干扰，按需调整
  • 休息 每隔一段时间休息，只做强制性任务

很惭愧，工作刚开始一两年我少有计划，单纯凭借好奇心学习到了不少东西。大约从去年写年度总结开始才刚刚做一些计划。目前我使用微软to-do跟踪自己的计划进度和deadline效果显著，治好了我的拖延症。

简单来说《软技能》中阐述的几个观点我感觉十分受益：

  1. 要有计划
  2. 完成计划时保持专注
  3. 使用番茄工作法可以保证保证一段时间的专注， 同时还可以确定自己的工作效率， 总结不足提高自身效率，从而帮助自己精确且高效的指定计划
  4. 只有你完成了计划的工作，接下来的休息时间才能安心

这边年读书情况

这半年看的书比较少，但是刷题和博客总结写的多了些

技术类：
《sql反模式》推荐， 应该叫数据库结构设计的最佳实践
《软技能，代码之外的生存指南》 有很多事比代码更重要的多，推荐

心理类：
《你的灯亮着吗》 解决问题前，先要搞清楚问题的本质。 一般般

LeetCode 最长回文子串算法
发表更新算法 / 字符串1 分钟读完 (大约147个字)

LeetCode 最长回文子串算法

Manacher 算法 容易理解，实现起来也没什么大坑，复杂度还是 O(n)的， 花半个小时实现下很有意思

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public String longestPalindrome(String s) {        
        StringBuilder sb = new StringBuilder(2 + 2 * s.length());
        sb.append("^");
        for (int i = 0; i < s.length(); i++) {
            sb.append("#").append(s.charAt(i));
        }
        sb.append("#$");
        
        String s2 = sb.toString();
        
        int maxStart = 1, max = 0, rC = 1, rR = 1;
        int[] p = new int[s2.length()];
        
        for (int i = 1; i < s2.length() - 1; i++ ) {
            
            p[i] = i < rR ? Math.min(p[2 * rC - i], rR - i) : 0;
            
            while (s2.charAt(i+p[i]+1) == s2.charAt(i - p[i] - 1)) {
                p[i] = p[i]+1;
            }
            
            if (i + p[i] > rR) {
                rC = i;
                rR = i + p[i];
            }
            
            if (p[i] > max) {
                maxStart = i - p[i];
                max = p[i];
            }
        }
        

        return s2.substring(maxStart,maxStart + 2*max+1).replace("#", "");
    }
}
[项目] 多角色权限展示数据的一种实现
发表更新工作 / 挑战3 分钟读完 (大约428个字)

[项目] 多角色权限展示数据的一种实现

多角色权限如果遇到不同角色能看到不同的列可以怎么做

  • 逐行读取

最简单的解决方法，实现简单。但是在微服务中调用接口次数太多，性能很差。

  • 批量读取

实现较复杂，但是性能好很多，下面主要介绍这种方法的思路

批量读取

以分页读取数据为例：

  1. 读取第一页数据，包含需要展示数据的id和所属权限（多个）

为什么需要所属权限这个字段呢？ 因为决定能否看到这行是有你所拥有的所有权限决定的，而决定能否看到哪个列是由这行所拥有的权限决定的。

如何获取该行所拥有的权限呢，我的做法是分不同的权限查询结果通过union 组合起来

  1. 将第一页数据原始顺序保存， 然后按行拥有权限分组

记录原始顺序是因为后面分组后会打乱， 为什么要分组？分组后同样的查询才能聚合在一起，可以简化代码

  1. 根据权限分组多次查询所需要的字段，然后将查询结果合并

这里我使用的graphql来选择需要查询的字段

  1. 最后还原成原来的顺序

可以使用guava Ordering工具类方便生成Compartor

[]: https://blog.yamato.moe/2018/11/06/2018-11-06-biz/ “根据权限查询时避免角色切换的一种思路”
[]: https://blog.yamato.moe/2019/04/04/Mybatis%20ResultSetHandler_2019-04-04%20%E7%BB%AD/ “【片段】 Mybatis ResultSetHandler 实践-续”
[]: https://blog.yamato.moe/2019/01/09/Mybatis%20ResultSetHandler_2019-01-09/ “【片段】 Mybatis ResultSetHandler 实践”

LeetCode二叉树基础算法
发表更新算法 / 二叉树15 分钟读完 (大约2235个字)

LeetCode二叉树基础算法

树的高度

104. Maximum Depth of Binary Tree (Easy)

递归计算二叉树左右两边深度，取最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}

平衡树

110. Balanced Binary Tree (Easy)

递归遍历二叉树左右子树深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private boolean balance = true;
    
    public boolean isBalanced(TreeNode root) {
        visitTree(root);
        return balance;
    }
    
    private int visitTree(TreeNode root) {
        if (root == null) return 0;
        int left = visitTree(root.left);
        int right = visitTree(root.right);
        if (Math.abs(left - right) > 1 ) this.balance = false;
        return Math.max(left, right) + 1;
    }
}

两节点的最长路径

543. Diameter of Binary Tree (Easy)

递归遍历二叉树左右子树深度， 路径就是两边子树深度之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private int max;
        
    public int diameterOfBinaryTree(TreeNode root) {
        deep(root);
        return max;
    }
    
    private int deep(TreeNode root) {
        if (root == null) return 0;
        int left = deep(root.left);
        int right = deep(root.right);
        max = Math.max(max,left+right);
        return Math.max(left, right) + 1;
    }
}

翻转树

226. Invert Binary Tree (Easy)

递归交换左右子树的引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode right =root.right;
        root.right = invertTree(root.left);
        root.left = invertTree(right);
        return root;
    }
}

归并两棵树

617. Merge Two Binary Trees (Easy)

递归时如果其中一个节点是空，可以直接复用该节点。如果新建节点，需要拷贝节点的左右子树引用，递归时会用到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null ) return null;
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        TreeNode root =  new TreeNode(t1.val + t2.val);
        root.left = mergeTrees(t1.left, t2.left);
        root.right = mergeTrees(t1.right, t2.right);
        return root;
    }
}

判断路径和是否等于一个数

Leetcode : 112. Path Sum (Easy)

递归查询子树和是否等于目标和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.val == sum && root.left == null && root.right == null) return true;
        return  hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

统计路径和等于一个数的路径数量

437. Path Sum III (Easy)

双层递归

  1. 以当前节点为起点统计路径和
  2. 当前节点以下节点为起点统计路径和

以root为根节点的路径数量= 以root为起点统计路径和+root左节点为起点统计路径和+root右节点为起点统计路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        //结果数 等于 以当前root为父节点和 root以下为父节点结果数之和
        return sum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    // 计算以当前node为父节点能都多少路径数
    private int sum(TreeNode node, int sum) {
        if (node == null) return 0;
        int count = 0;
        if (node.val == sum) count++;
        count += sum(node.left, sum - node.val) + sum(node.right, sum - node.val);
        return count;
    }
}

子树

572. Subtree of Another Tree (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;
        return isSubRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    
    public boolean isSubRoot(TreeNode node, TreeNode t) {
        if (node == null && t == null) return true;
        if (node == null || t == null) return false;
        if (node.val != t.val) return false;
        return isSubRoot(node.left, t.left) && isSubRoot(node.right, t.right); 
    }
}

树的对称

101. Symmetric Tree (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetric(root.left, root.right);
    }
    
    public boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
}

最小路径

111. Minimum Depth of Binary Tree (Easy)

和最大路径类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (left == 0 || right == 0) return left + right + 1;
        return Math.min(left, right) + 1;
    }
}

统计左叶子节点的和

404. Sum of Left Leaves (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        if (root.left != null && root.left.left == null && root.left.right == null) return root.left.val + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
}
````

#### 相同节点值的最大路径长度

[687. Longest Univalue Path (Easy)](https://leetcode.com/problems/longest-univalue-path/)

递归查找左右子树相同节点值最大路径，最大路径的计算：如果相等路径+1，如果不相等置为0。

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int path = 0;
    
    public int longestUnivaluePath(TreeNode root) {
        visit(root);
       return path; 
    }
    
    private int visit(TreeNode root) {
        if  (root == null) return 0;
        int left = visit(root.left);
        int right = visit(root.right);
        
        left =  (root.left != null && root.val == root.left.val) ? left + 1 : 0;
        right = (root.right != null && root.val == root.right.val)? right + 1 : 0;
        path = Math.max(path, left+right);
        return Math.max(left, right );
    }
}

间隔遍历

337. House Robber III (Medium)

递归查询两种情况

  1. 如果从当前节点开始
  2. 从当前节点的子节点开始
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int val1 = root.val, val2 = 0;
        if (root.left != null) val1+= rob(root.left.left) + rob(root.left.right);
        if (root.right != null) val1+= rob(root.right.left) + rob(root.right.right);
        
        val2 = rob(root.left) + rob(root.right);
        return Math.max(val1, val2);
    }
}

找出二叉树中第二小的节点

Second Minimum Node In a Binary Tree (Easy)

第二小节点在子树节点上，如果子树值与根节点相等，继续向下查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) return -1;
        if (root.left == null) return -1;
        int left = root.left.val, right = root.right.val;
        if (root.val == root.left.val) left = findSecondMinimumValue(root.left);
        if (root.val == root.right.val) right = findSecondMinimumValue(root.right);
        if (left != -1 && right != -1) return Math.min(left, right);
        if (left > -1) return left;
        return right;
    }
}

二叉树的层平均值

637. Average of Levels in Binary Tree (Easy)

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            double sum = 0d;
            
            for(int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                sum+= node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            ret.add(sum/count);
        }
        return ret;
    }
}

找树左下角的值

513. Find Bottom Left Tree Value (Easy)

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int val = 0;
    
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return val;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            // 这一行的数量
            int count = queue.size();
            
            for (int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                if(i == 0) val = node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return val;
    }
}

非递归实现二叉树的后序遍历

入栈条件： 未访问过该节点
出栈条件： 访问过该节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private List<Integer> res = new LinkedList<>();
    private Stack<TreeNode> stack = new Stack<>();
    private Set<TreeNode> visited = new HashSet<>();
    
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return res;
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            
            if ((node.left == null && node.right == null) || visited.contains(node)) {
                TreeNode i = stack.pop();
                res.add(i.val);
            } else {
                visited.add(node);
                if (node.right != null)
                    stack.push(node.right);
                if (node.left != null) 
                    stack.push(node.left);
            }
        }
        return res;
    }
    
    private void visit(TreeNode root) {
        if(root == null) return;
        visit(root.left);
        visit(root.right);
        res.add(root.val);
    }
}

非递归实现二叉树的前序遍历

入栈条件： 无
出栈条件： 直接出栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> res = new LinkedList<>();
    private Stack<TreeNode> stack = new Stack<>();
    
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return res;
        stack.push(root);
        
        while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                res.add(node.val);
                if (node.right != null) stack.push(node.right);
                if (node.left != null)  stack.push(node.left);
        }
        return res;
    }
}

非递归实现二叉树的中序遍历

入栈条件： 未访问过该节点
出栈条件： 访问过该节点
入栈顺序: right -> middle -> left

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> res = new LinkedList<>();
    private Stack<TreeNode> stack = new Stack<>();
    private Set<TreeNode> visited = new HashSet<>();
    
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return res;
        push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if ((node.left == null && node.right == null) || visited.contains(node)) {
                res.add(node.val);
            } else {
                push(node);
            }
        }
        return res;
    }
    
    private void push(TreeNode root) {
        if (root == null) return;
        visited.add(root);
        if (root.right != null) stack.push(root.right);
        stack.push(root);
        if (root.left != null) stack.push(root.left);
    }
}
LeetCode 二叉树排序树基础算法
发表更新算法 / 二叉树8 分钟读完 (大约1178个字)

LeetCode 二叉树排序树基础算法

修剪二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return null;
        if (root.val < L) return trimBST(root.right, L, R);
        if (root.val > R) return trimBST(root.left, L, R);
        root.left = trimBST(root.left, L, R);
        root.right = trimBST(root.right, L, R);
        return root;
    }
}

二叉搜索树中第K小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int cnt;
    private int val;
    
    public int kthSmallest(TreeNode root, int k) {
        search(root, k);
        return val;
    
    }
    
    private void search(TreeNode root, int k) {
        if (root == null) return;
        // 
        kthSmallest(root.left, k);
        cnt++;
        if (cnt == k) {
            val =  root.val;
            return;
        }
        kthSmallest(root.right, k);
    }
}

把二叉搜索树转换为累加树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private int sum;
    
    public TreeNode convertBST(TreeNode root) {
        // 中序遍历 但是是从右往左遍历
        // 
        visit(root);
        return root;
    }
    
    
    private void visit(TreeNode root) {
        if (root == null) return;
        
        visit(root.right);
         sum += root.val;
    
        root.val = sum;
        
        visit(root.left);
    }
}

二叉搜索树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 公共祖先在左边
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        // 公共祖先在右边
        if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        // 公共祖先在这
        return root;
    }
}

二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // 左右都是父节点， 上一级就是公共父节点
        if(left != null && right != null) return root;
        if (left == null && right == null) return null;
        if (left != null) return left;
        return right;
    }
}

将有序数组转换为二叉搜索树

二叉树中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length -1);
    }
    
    
    private TreeNode build(int[] nums, int start, int end) {
        
        if(start> end) return null;
        
        TreeNode node = new TreeNode(nums[(start+end)/2]);
        
        node.left = build(nums, start, (start+end)/2 -1);
        node.right = build(nums, (start+end)/2+1, end);
        return node;
    }
}

有序链表转换二叉搜索树

链表转数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new LinkedList();
        ListNode now = head;
        while (now != null) {
            list.add(now.val);
            now = now.next;
        }
        
        return build(list, 0, list.size() - 1);
    }
    
    
    private TreeNode build(List<Integer> nums, int start, int end) {
        
        if(start> end) return null;
        
        TreeNode node = new TreeNode(nums.get((start+end)/2));
        
        node.left = build(nums, start, (start+end)/2 -1);
        node.right = build(nums, (start+end)/2+1, end);
        return node;
    }
}

还可以使用双指针找到链表中间节点，缺点是重复遍历节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
//         List<Integer> list = new LinkedList();
//         ListNode now = head;
//         while (now != null) {
//             list.add(now.val);
//             now = now.next;
//         }
        
//         return build(list, 0, list.size() - 1);
        
        return sortedListToBST(head, null);
        
        

    }
    
    private TreeNode sortedListToBST(ListNode head, ListNode tail) {
        if (head == tail) return null;
        
        ListNode mid = head, end = head;
        while (end != tail && end.next != tail) {
            mid = mid.next;
            end = end.next.next;
        }
        
        TreeNode root = new TreeNode(mid.val);
        root.right = sortedListToBST(mid.next, tail);
        root.left = sortedListToBST(head, mid);
        return root;
    }
    
    
    private TreeNode build(List<Integer> nums, int start, int end) {
        
        if(start> end) return null;
        
        TreeNode node = new TreeNode(nums.get((start+end)/2));
        
        node.left = build(nums, start, (start+end)/2 -1);
        node.right = build(nums, (start+end)/2+1, end);
        return node;
    }
    
}

两数之和 IV - 输入 BST

自己写两次遍历搜索二叉树，注意要排除自身节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private boolean res;
    private TreeNode r;
    private TreeNode current;
    
    
    public boolean findTarget(TreeNode root, int k) {
        r = root;
        visit(root, k);
        return res;
    }
    
    private void visit(TreeNode root, int val) {
        if (root == null) return;
        visit(root.left, val);
        current = root;
        if (find(r, val - root.val)) {res = true; return;}
        visit(root.right, val);
    }
    
    private boolean find(TreeNode root, int value) {
        if (root == null) return false;
        if (root == current) return false;
        if (root.val == value ) return true;
        return  (value > root.val) ? find(root.right, value): find(root.left, value);
    }
}

正经思路， 中序遍历转化为排序数组， 使用双指针查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private List<Integer> res = new ArrayList<>(64);
    
    public boolean findTarget(TreeNode root, int k) {

        visitTree(root);
        
        int low = 0, high = res.size() - 1;
        while (low < high) {
            int sum = res.get(low) + res.get(high);
            if (sum == k) return true;
            if (sum < k) low++;
            else high--;
        }
        return false;
        
    }
    

    
    private void visitTree(TreeNode root) {
        if (root == null) return;
        visitTree(root.left);
        res.add(root.val);
        visitTree(root.right);        
    }

}
IO Modle
发表更新Java基础7 分钟读完 (大约1006个字)

IO Modle

操作系统IO模型与Java IO

Java IO模型和操作系统IO模型息息相关，之前阻塞/非阻塞，同步/非同步之间的关系一直分不清，所以很有必要了解下操作系统(linux)提供了哪些接口来进行IO。目前我们只需要了解即可，使用相关可以直接查看java io教程。

最基础的知识

以使用IO读取数据为例，一般操作系统分为两个独立的阶段进行操作：

  1. 等待数据准备完成，可以是从磁盘拷贝到内核空间，或者是网卡接受到数据后拷贝到内核空间。
  2. 从内核空间将数据拷贝至请求数据的进程。如果是java可能还需从进程拷贝至jvm堆内存。

Blocking I/O Model

这个是最常用的模型，望文生义就是阻塞IO，进行IO的两个阶段会都阻塞程序，直到读取到数据或者返回错误才会返回。

blocking io

具体来说，通过调用系统recvfrom函数，而recvfrom函数会等到出错或者把数据拷贝到进程完成时才会返回。之后我们程序只需要处理错误或者处理数据就可以了。

阻塞模型对应java中绝大部分IO操作，比如网络请求api，io stream api，该模型优点在于简单直观，缺点在长时间阻塞很难支持大量并发IO请求。

Nonblocking I/O Model

该模型在java中没有对应，所以这里只做简单介绍。

nonblocking io

使用轮询方式调用系统recvfrom函数，recvfrom函数在第一阶段完成前一直返回错误，直到第一阶段完成后，阻塞至第二阶段完成。

这个模型稍显鸡肋，特点是在第一阶段是非阻塞的（进程不会被切换），代码相比阻塞模型来说也更复杂。

I/O Multiplexing Model

非常著名的IO模型，可以支持大量并发IO。通过调用select或者pull并阻塞，而不是在实际调用系统IO时阻塞。使用select阻塞在第一阶段和Blocking I/O的阻塞不太一样，Blocking I/O阻塞在当前IO操作第一阶段，而I/O复用则可以注册多个I/O在select函数，当有一个I/O就绪时select函数就会返回，如果所有I/O处于第一阶段阻塞状态则select函数阻塞。

multiplexing io

相比较Blocking I/O Model和Nonblocking I/O Model，I/O Multiplexing Model明显能在短时间内处理更多的I/O。如果使用多线程+Blocking I/O Model也能达到类似的效果，但是有可能消耗过多线程资源。

I/O Multiplexing Model对应java NIO的Selector等api

Signal-Driven I/O Model

该模型在java中没有对应，所以这里只做简单介绍。

Signal-Driven I/O

该模型特点是第一阶段调用sigaction函数非阻塞返回，在第一阶段完成后发送信号SIGIO至进程，之后在signal handler中进行第二阶段处理。相当于对Nonblocking I/O Model的一种改进。

Asynchronous I/O Model

Asynchronous I/O Model相比较Signal-Driven I/O Model的区别在于通知的时机不同：Asynchronous I/O Model在第一和第二阶段都完成时通过信号通知进程操作完成。

Asynchronous I/O Model

Asynchronous I/O Model对应java中AsynchronousSocketChannel，AsynchronousServerSocketChannel 和 AsynchronousFileChannel等api。

各个模型比较

[1]: https://notes.shichao.io/unp/ch6/ “Chapter 6. I/O Multiplexing: The select and poll Functions”

关注我

链接

分类

最新文章

归档

标签

IM系统1
aop1
java14
linux1
mybatis5
redis1
spring2
中间件2
代码23
分布式7
团队1
工作24
感悟3
搜索1
操作系统1
数据库5
架构2
消息3
消息队列2
算法7
缓存6
读书8
×