这个是因该很早之前就要学习的东西，一直拖今天，惭愧…

本文是 labuladong的算法笔记的读书笔记

Data Structures

一、数据结构的存储方式

本质上讲，数据结构的存储方式只有两种：数组和链表

根本结构：	数组	链表
存储方式：	顺序存储	链式存储
实现队列和栈：	处理扩容缩容问题	需要更多的内存空间存储结点指针
图：	邻接矩阵	邻接表
散列表（通过散列函数把键映射到一个大数组里）：	线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些	对于解决散列冲突的方法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针
Redis：	Redis底层的存储方式直晒都提供了两种	来根据存储数据的实际情况是用合适的存储方式
优点和缺点：	数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 `O(N)`；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 `O(N)`。	链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 `O(1)`。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

二、数据结构的基本操作

数据结构种类很多，但它们存在的目的都是在不同的应用场景，尽可能高效地增删查改。

如何遍历 + 访问？我们仍然从最高层来看，各种数据结构的遍历 + 访问无非两种形式：线性的和非线性的。

线性	非线性
for/while	递归

基本的链表遍历框架

/* 基本的单链表节点 */
class ListNode {
    int val;
    ListNode next;
}

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // 迭代访问 p.val
    }
}

void traverse(ListNode head) {
    // 递归访问 head.val
    traverse(head.next)
}

二叉树遍历框架，典型的非线性递归遍历结构：

/* 基本的二叉树节点 */
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    traverse(root.left)
    traverse(root.right)
}

二叉树框架可以扩展为 N 叉树的遍历框架：

/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child);
}

因为图就是好几 N 叉棵树的结合体，环状图用个布尔数组 visited 做标记就行了。

三、算法刷题指南

首先要明确的是，数据结构是工具，算法是通过合适的工具解决特定问题的方法。也就是说，学习算法之前，最起码得了解那些常用的数据结构，了解它们的特性和缺陷。

先刷二叉树，原因：

因为二叉树是最容易培养框架思维的，而且大部分算法技巧，本质上都是树的遍历问题。

二叉树的解题框架

void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

比如：

LeetCode 124 题，难度 Hard，让你求二叉树中最大路径和，主要代码如下：

int ans = INT_MIN;
int oneSideMax(TreeNode* root) {
    if (root == nullptr) return 0;
    int left = max(0, oneSideMax(root->left));
    int right = max(0, oneSideMax(root->right));
    ans = max(ans, left + right + root->val);
    return max(left, right) + root->val;
}

LeetCode 105 题，难度 Medium，让你根据前序遍历和中序遍历的结果还原一棵二叉树，很经典的问题吧，主要代码如下：

TreeNode buildTree(int[] preorder, int preStart, int preEnd, 
    int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {

    if(preStart > preEnd || inStart > inEnd) return null;

    TreeNode root = new TreeNode(preorder[preStart]);
    int inRoot = inMap.get(root.val);
    int numsLeft = inRoot - inStart;

    root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, 
                          inorder, inStart, inRoot - 1, inMap);
    root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, 
                          inorder, inRoot + 1, inEnd, inMap);
    return root;
}

不要看这个函数的参数很多，只是为了控制数组索引而已，本质上该算法也就是一个前序遍历。

LeetCode 99 题，难度 Hard，恢复一棵 BST，主要代码如下：

void traverse(TreeNode* node) {
    if (!node) return;
    traverse(node->left);
    if (node->val < prev->val) {
        s = (s == NULL) ? prev : s;
        t = node;
    }
    prev = node;
    traverse(node->right);
}

这不就是个中序遍历嘛，对于一棵 BST 中序遍历意味着什么，应该不需要解释了吧。

你看，Hard 难度的题目不过如此，而且还这么有规律可循，只要把框架写出来，然后往相应的位置加东西就行了，这不就是思路吗。

对于一个理解二叉树的人来说，刷一道二叉树的题目花不了多长时间。那么如果你对刷题无从下手或者有畏惧心理，不妨从二叉树下手，前 10 道也许有点难受；结合框架再做 20 道，也许你就有点自己的理解了；刷完整个专题，再去做什么回溯动规分治专题，你就会发现只要涉及递归的问题，都是树的问题。

上面的总结是该UP主给出的解题思路，说实话，看懂是不可能看懂的，先继续往后面刷。

继续往后面copy没啥意思，反正就是突出这个框架的重要性。

这就是框架的力量，能够保证你在快睡着的时候，依然能写出正确的程序；就算你啥都不会，都能比别人高一个级别。

四、总结几句

数据结构的基本存储方式就是链式和顺序两种，基本操作就是增删查改，遍历方式无非迭代和递归。

刷算法题建议从「树」分类开始刷，结合框架思维，把这几十道题刷完，对于树结构的理解应该就到位了。这时候去看回溯、动规、分治等算法专题，对思路的理解可能会更加深刻一些。

后面在本章中还介绍了一些针对细节的解题框架，我决定谨遵作者的嘱托先刷树。

五、时间复杂度和空间复杂度

这里仅仅介绍时间复杂度和空间复杂度的入门部分，后续如果要用到详细的部分，我会再补充。

1. 说明

时间复杂度：就是说执行算法需要消耗的时间长短，越快越好。比如你在电脑上打开计算器，如果一个普通的运算要消耗1分钟时间，那谁还会用它呢，还不如自己口算呢。
空间复杂度：就是说执行当前算法需要消耗的存储空间大小，也是越少越好。本来计算机的存储资源就是有限的，如果你的算法总是需要耗费很大的存储空间，这样也会给机器带来很大的负担。

2.常见的时间复杂度量级

我们一般用“大O符号表示法”来表示时间复杂度：T(n) = O(f(n))
n是影响复杂度变化的因子，f(n)是复杂度具体的算法。

常数阶O(1)
线性阶O(n)
对数阶O(logN)
线性对数阶O(nlogN)
平方阶O(n²)
立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)

T(n) = O((f(n))

T(n) 表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以表示为，推导过程：

1 2	T(n) = O(2n+2) -> T(n) = O(n) T(n) = O(2n2+2n+3) -> T(n) = O(n2)

常数阶O(1)

1
2
3

int a = 1;
int b = 2;
int c = 3;

我们假定每执行一行代码所需要消耗的时间为1个时间单位，那么以上3行代码就消耗了3个时间单位。那是不是这段代码的时间复杂度表示为O(n)呢？

其实不是的，*因为大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。***
*上面的算法并没有随着某个变量*的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。

线性阶O(n)

for(i = 1; i <= n; i++) {
   j = i;
   j++;
}

第1行会执行1次，第2行和第3行会分别执行n次，总的执行时间也就是 2n + 1 次，那它的时间复杂度表示是 O(2n + 1) 吗？ No !
还是那句话：“**大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的**”。
所以它的时间复杂度其实是O(n);

对数阶O(logN)

平方阶O(n²)int i = 1;
while(i < n) {
    i = i * 2;
}

可以看到每次循环的时候 i 都会乘2，那么总共循环的次数就是log2n，因此这个代码的时间复杂度为O(logn)。
这儿有个问题，为什么明明应该是O(log2n）,却要写成O(logn)呢？
其实这里的底数对于研究程序运行效率不重要，写代码时要考虑的是数据规模n对程序运行效率的影响，常数部分则忽略，同样的，如果不同时间复杂度的倍数关系为常数，那也可以近似认为两者为同一量级的时间复杂度。

线性对数阶O(nlogN)

for(m = 1; m < n; m++) {
    i = 1;
    while(i < n) {
        i = i * 2;
    }
}

线性对数阶w的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

平方阶O(n²)

for(x = 1; i <= n; x++){
   for(i = 1; i <= n; i++) {
       j = i;
       j++;
    }
}

把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。

O(m+n) 、O(m*n)

function cal(m, n) {
  var sum_1 = 0;
  var i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }
  var sum_2 = 0;
  var j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }
  return sum_1 + sum_2;
}

从代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(n))。

数据结构操作的复杂性

数据结构	连接	查找	插入	删除
数组	1	n	n	n
栈	n	n	1	1
队列	n	n	1	1
链表	n	n	1	1
哈希表	-	n	n	n
二分查找树	n	n	n	n
B树	log(n)	log(n)	log(n)	log(n)
红黑树	log(n)	log(n)	log(n)	log(n)
AVL树	log(n)	log(n)	log(n)	log(n)

数组排序算法的复杂性

名称	最优	平均	最坏	内存	稳定
冒泡排序	n	n^2	n^2	1	Yes
插入排序	n	n^2	n^2	1	Yes
选择排序	n^2	n^2	n^2	1	No
堆排序	n log(n)	n log(n)	n log(n)	1	No
归并排序	n log(n)	n log(n)	n log(n)	n	Yes
快速排序	n log(n)	n log(n)	n^2	log(n)	No
希尔排序	n log(n)	取决于差距序列	n (log(n))^2	1	No

时间复杂度分析

三个使用分析方法：

只关注循环执行次数最多的的一段代码

大 O 这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以，我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。

1 function cal(n) {
2    var sum = 0;
3    var i = 1;
4    for (; i <= n; ++i) {
5      sum = sum + i;
6    }
7    return sum;
8  }

2.3行代码都是常量级别的执行时间，与n的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是滴4、5行代码，所以这块代码要重点分析。那两行代码执行了n次，所以总的时间复杂度就是O(n)

加法法则：总复杂度等于量级最大的那段代码的复杂度

综合这三段代码的时间复杂度(分别是O(1), O(n), O(n2))，我们取其中最大的量级。所以，整段代码的时间复杂度就为 O(n2)。也就是说：总的时间复杂度就等于量级最大的那段代码的时间复杂度。那我们将这个规律抽象成公式就是：

如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，类似嵌套循环的，都是用乘法来处理

大O

大O描述的是算法的运行时间和输入数据之间的关系

以下是一些最常用的大O标记法列表以及它们与不同大小输入数据的性能比较。

大O标记法	计算10个元素	计算100个元素	计算1000个元素
O(1)	1	1	1
O(log N)	3	6	9
O(N)	10	100	1000
O(N log N)	30	600	9000
O(N^2)	100	10000	1000000
O(2^N)	1024	1.26e+29	1.07e+301
O(N!)	3628800	9.3e+157	4.02e+2567

3.常见空间复杂度计算

空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)。

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。

空间复杂度 O(n)

int[] m = new int[n]
for(i = 1; i <= n; ++i) {
   j = i;
   j++;
}

空间复杂度分析

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。

类比一下，空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。

最好最坏情况时间复杂度

最简单的例子，如果我们在某个数组中查找某个元素，这个元素可能在各个位置，然后我们一旦找到了这个元素立即跳出循环，这段代码的时间复杂度还是 O(n) 吗？

我们需要引入三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。

总之分析下来，最好情况时间复杂度没有啥意义，最坏情况时间复杂度和平均情况时间貌似区别不大？后续有新的理解会更新上来。

均摊时间复杂度

大部分情况下，我们并不需要区分最好、最坏、平均三种复杂度。平均复杂度只在某些特殊情况下才会用到，而均摊时间复杂度应用的场景比它更加特殊、更加有限。找出所有的输入情况及相应的发生概率，然后再计算加权平均值。

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

Ex. 某段代码实现了一个往数组中插入数据的功能。当数组满了之后，也就是代码中的 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。

那这段代码的时间复杂度是多少呢？你可以先用我们刚讲到的三种时间复杂度的分析方法来分析一下。

最理想的情况下，数组中有空闲空间，我们只需要将数据插入到数组下标为 count 的位置就可以了，所以最好情况时间复杂度为 O(1)。最坏的情况下，数组中没有空闲空间了，我们需要先做一次数组的遍历求和，然后再将数据插入，所以最坏情况时间复杂度为 O(n)。

那平均时间复杂度是多少呢？答案是 O(1)。我们还是可以通过前面讲的概率论的方法来分析。

假设数组的长度是 n，根据数据插入的位置的不同，我们可以分为 n 种情况，每种情况的时间复杂度是 O(1)。除此之外，还有一种“额外”的情况，就是在数组没有空闲空间时插入一个数据，这个时候的时间复杂度是 O(n)。而且，这 n+1 种情况发生的概率一样，都是 1/(n+1)。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是：

O(1)

至此为止，前面的最好、最坏、平均时间复杂度的计算，理解起来应该都没有问题。但是这个例子里的平均复杂度分析其实并不需要这么复杂，不需要引入概率论的知识。这是为什么呢？我们先来对比一下这个 insert() 的例子和前面那个 find() 的例子，你就会发现这两者有很大差别。

首先，find() 函数在极端情况下，复杂度才为 O(1)。但 insert() 在大部分情况下，时间复杂度都为 O(1)。只有个别情况下，复杂度才比较高，为 O(n)。这是 insert()第一个区别于 find() 的地方。

我们再来看第二个不同的地方。对于 insert() 函数来说，O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，一般都是一个 O(n) 插入之后，紧跟着 n-1 个 O(1) 的插入操作，循环往复。

所以，针对这样一种特殊场景的复杂度分析，我们并不需要像之前讲平均复杂度分析方法那样，找出所有的输入情况及相应的发生概率，然后再计算加权平均值。

针对这种特殊的场景，我们引入了一种更加简单的分析方法：摊还分析法，通过摊还分析得到的时间复杂度我们起了一个名字，叫均摊时间复杂度。

那究竟如何使用摊还分析法来分析算法的均摊时间复杂度呢？

我们还是继续看在数组中插入数据的这个例子。每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。这就是均摊分析的大致思路。

均摊时间复杂度我没有去深刻理解，没必要看这个冷门知识点看睡着了。

对数据规模有一个概念和分析

想要在1s内解决问题：

O(n2)的算法可以处理大约10^4级别的数据
O(n)的算法可以处理大约10^8级别的数据
O(nlogn)的算法可以处理大约10^7级别的数据
保险起见，在实际处理过程中最好降一个级

4.递归算法复杂度分析

鉴于我对递归的使用并不熟练，这个坑放在这，日后来填。

5.避免复杂度的震荡

常见场景：

java数组动态扩容

假设我们现在有一个数组，这个数组的容量为n，并且现在也装满了元素，那么现在我们再调用一下addLast操作，显然在添加一个新的元素的时候会需要扩容（扩容会耗费O(N)的时间），之后我们马上进行removeLast操作（根据我们之前的逻辑，在上一个操作里通过扩容，容量变为了2n，在我们删除1个元素之后，元素又变为了n = 2n/2，根据我们代码中的逻辑，会触发缩容的操作，同样耗费了O(n)的时间）；那么我们如果再addLast、removeLast…等相继依次操作。

对于addLast和removeLast来说，都是每隔n次操作都会触发resize，而不会每次都触发
但是现在我们制造了一种情景：同时看addLast和removeLast的时候，每一次都会耗费O(n)的复杂度，那么这就是复杂度的震荡

resize的复杂度分析——出现复杂度震荡的原因及解决方案

removeLast时resize过于着急（采用了Eager的策略: 一旦我们的元素变为当前容积的1/2的时候，我们马上就把当前的容积也缩容为1/2）
解决方案: Lazy （在线段树中，也会用到类似的思路）
当元素变为当前容积的1/2时，不着急把当前容积缩容，而是等等；如果后面一直有删除操作的话，当删除元素到整个数组容积的1/4时，那么这样看来我们的数组确实用不了这么大的容积，此时我们再来进行缩容，缩容整个数组的1/2（这样，即便我们要添加元素，也不需要马上触发扩容操作）

当 size == capacity / 4时，才将capacity减半！

这里只谈了如何避免，却没有说为什么要避免。

6. 复杂度分析的4个概念

一、复杂度分析的4个概念

1.最坏情况时间复杂度：代码在最理想情况下执行的时间复杂度。
2.最好情况时间复杂度：代码在最坏情况下执行的时间复杂度。
3.平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。
4.均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

二、为什么要引入这4个概念？

1.同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这4个概念。

2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。

三、如何分析平均、均摊时间复杂度？

1.平均时间复杂度

代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。

2.均摊时间复杂度

两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

7.常用排序算法

排序晚点再来看

《算法第四版》是肯定要看的，到时候再来完备整个复杂度体系。

六、实操

在经过了上面得简单梳理之后，没啥好说得，开始自己的实际操作。

链表

链表（Linked List）数据结构概览

链表（Linked List）是线性表的一种（线性表包含顺序表与链表），通过指针将一系列位于不连续的内存空间中的元素连接起来，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理，但也失去了快速随机存取的优点，同时增大了内存开销（存储指针域）。

链表数据结构由一连串节点（Node）组成，每个节点包含数据域（Data Fields）和一或两个用来指向上一个/或下一个节点位置的指针域（Pointer Fields）。链表可以方便地插入或移除表中任意位置的节点，但是随机存取效率不高。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

链表（Linked List）数据结构操作接口

我们将要使用 Java 语言手写一枚链表数据结构。首先，明确链表数据结构所具有的操作接口方法。

接口方法	解释说明
`void addFirst(E element)`	向链表头部添加一个新的元素。
`void addLast(E element)`	向链表尾部添加一个新的元素。
`E removeFirst()`	移除链表头部第一个元素。
`E removeLast()`	移除链表尾部最后一个元素。
`E getFirst()`	返回链表头部第一个元素。
`E getLast()`	返回链表尾部最后一个元素。
`boolean contains(E element)`	检查链表中是否包含指定元素。
`E insert(int index, E element)`	向链表指定索引位置插入新元素。
`E get(int index)`	返回链表中指定索引的元素。
`E set(int index, E element)`	为链表中指定索引的元素设新值。
`E remove(int index)`	移除链表中指定索引的元素。
`boolean remove(E element)`	移除链表中指定的元素。
`int indexOf(E element)`	返回指定元素所在链表的索引，元素不存在则返回`-1`，若存在多个相同元素，则返回第一次出现的索引下标。
`int size()`	返回链表存储元素数量。
`boolean isEmpty()`	检查链表是否为空。
`void clear()`	清空链表。
`String toString()`	返回链表的字符串形式。

单向链表（Single Linked List）

我们使用 Java 语言实现一枚简单的单向链表。顾名思义，单向链表只能做单向遍历（头节点 -> 尾节点），因为单向链表的节点（Node）只包含数据域和一个指针域（指向下一个节点）。

我们来定义出单链表中节点（Node）的数据结构，使用泛型类提高节点存储数据的灵活性。节点数据结构包含构造方法，两个私有变量：数据域和指针域，及其对应的Getter/Setter公开方法。

/**
 * @program: draft
 * @description: 单链表中节点（Node）
 * @author: Fly.Hugh
 * @create: 2020-07-22 22:55
 **/
public class Node<E> {
    /**
     * 数据域
     */
    private E elem;
    /**
     * 指针域
     */
    private Node<E> next;
    /**
     * 构造方法
     */
    public Node(E element, Node<E> next) {
        this.elem = element;
        this.next = next;
    }
    /**
     * 无参构造方法
     */
    public Node() {
        this(null, null);
    }
    /* Setter & Getter */
    public void setElem(E element) {
        this.elem = element;
    }
    public E getElem() {
        return this.elem;
    }
    public void setNext(Node<E> next) {
        this.next = next;
    }
    public Node<E> getNext() {
        return this.next;
    }
}

考虑单链表数据结构：单链表包含一枚头节点（Head），头结点不存储数据，而是指向第一个实际存储数据的节点；尾节点可以被定义为指针域为null的最后一枚节点。

这边先把单向链表的完整代码放出来，后面再放出讲解


import java.util.NoSuchElementException;

/**
 * @program: draft
 * @description: 单链表
 * @author: Fly.Hugh
 * @create: 2020-07-22 23:02
 **/
public class SingleLinkedList<E> {

    /**
     * 链表头节点
     */
    private Node<E> head;

    /**
    * @author fly.hugh
    * @Description
    * @Date 23:26 2020/7/22
    * @Param []
    * @return
    **/
    public SingleLinkedList() {
        this.head = new Node<E>();
    }

    /**
     * 向链表头部添加一个新的元素（头插法）。
     * @param element
     * @return void
     */
    public void addFirst(E element) {
        Node<E> node = new Node<E>(element, null);
        node.setNext(head.getNext());
        head.setNext(node);
    }

    /**
     * 向链表尾部添加一个新的元素（尾插法）。
     * @Param []
     * @return void
     */
    public void addLast(E element) {
        Node<E> node = new Node<E>(element, null);
        Node<E> tail = head;
        while (tail.getNext() != null) {
            tail = tail.getNext();
        }
        tail.setNext(node);
    }

    /**
     * 取得链表头部第一个元素，链表为空则抛出异常。
     * @Param []
     * @return First element of {@code LinkedList}.
     * @throws NoSuchElementException if this {@code LinkedList} is empty.
     */
    public E getFirst() throws NoSuchElementException {
        if (head.getNext() == null) {
            throw new NoSuchElementException();
        }
        return head.getNext().getElem();
    }
    /**
     * 取得链表尾部最后一个元素，链表为空则抛出异常。
     * @Param []
     * @return Last element of {@code LinkedList}.
     * @throws NoSuchElementException if this {@code LinkedList} is empty.
     */
    public E getLast() throws NoSuchElementException {
        Node<E> tail = head;
        while (tail.getNext() != null) {
            tail = tail.getNext();
        }
        if (tail == head) {
            throw new NoSuchElementException();
        }
        return tail.getElem();
    }

    /**
     * 计算链表存储元素数量。
     * @Param []
     * @return Size of elements in {@code LinkedList}.
     */
    public int size() {
        int cnt = 0;
        for (Node<E> n = head; n.getNext() != null; n = n.getNext()) {
            ++cnt;
        }
        return cnt;
    }
    /**
     * 检查链表是否为空。
     * @Param []
     * @return Boolean {@code true} or {@code false}.
     */
    public boolean isEmpty() {
        return head.getNext() == null ? true : false;
    }
    /**
     * 检查链表是否为空。
     * @Param []
     * @return Boolean {@code true} or {@code false}.
     */
    public boolean _isEmpty() {
        return this.size() > 0 ? false : true;
    }

    /**
     * 返回并移除链表头部第一个元素。
     * @Param []
     * @return First element of this {@code Linked List}.
     * @throws NoSuchElementException
     */
    public E removeFirst() throws NoSuchElementException {
        if (this.isEmpty()) {
            throw new NoSuchElementException();
        }
        Node<E> first = head.getNext();
        head.setNext(
                first.getNext()
        );
        return first.getElem();
    }

    /**
     * 返回并移除链表尾部最后一个元素。
     * @Param []
     * @return Last element of this {@code Linked List}.
     * @throws NoSuchElementException
     */
    public E removeLast() throws NoSuchElementException {
        if (this.isEmpty()) {
            throw new NoSuchElementException();
        }
        Node<E> prev = head;
        while (prev.getNext().getNext() != null) {
            prev = prev.getNext();
        }
        Node<E> last = prev.getNext();
        prev.setNext(null);
        return last.getElem();
    }

    /**
     * 检查链表中是否包含目标元素，
     * 元素相等使用 {@code o.equals(obj)} 判断。
     * @param element
     * @return Boolean
     */
    public boolean contains(E element) {
        for (Node<E> current = head.getNext();
             current != null;
             current = current.getNext()) {
            if (element.equals(current.getElem())) {
                return true;
            }
        }
        return false;
    }

    /**
     * 返回指定元素所在链表的索引。
     * @param element
     * @return The index of element in {@code LinkedList},
     *  return {@code -1} if element does not found.
     */
    public int indexOf(E element) {
        int index = 0;
        for (Node<E> current = head.getNext();
             current != null;
             current = current.getNext()) {
            if (element.equals(current.getElem())) {
                return index;
            }
            ++index;
        }
        return -1;
    }

    /**
     * 获取链表指定索引的元素。
     * @param index
     * @return element
     * @throws IndexOutOfBoundsException
     */
    public E get(int index) throws IndexOutOfBoundsException {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> n = head.getNext();
        while (index > 0) {
            n = n.getNext();
            --index;
        }
        return n.getElem();
    }

    /**
     * 为链表指定索引位置的元素设新值。
     * @param index
     * @param element
     * @return Previous element in the index.
     * @throws IndexOutOfBoundsException
     */
    public E set(int index, E element) throws IndexOutOfBoundsException {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> n = head.getNext();
        while (index > 0) {
            n = n.getNext();
            --index;
        }
        E oldValue = n.getElem();
        n.setElem(element);
        return oldValue;
    }

    /**
     * 移除链表指定索引下标元素。
     * @param index
     * @return Removed element
     * @throws IndexOutOfBoundsException
     */
    public E remove(int index) throws IndexOutOfBoundsException {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
        index -= 1;
        Node<E> prev = head;
        while (index >= 0) {
            prev = prev.getNext();
            --index;
        }
        Node<E> current = prev.getNext();
        Node<E> next = current.getNext();
        prev.setNext(next);
        return current.getElem();
    }

    /**
     * 移除链表指定元素，
     * 操作成功返回{@code true}，不存在目标元素则返回{@code false}。
     * @param element
     * @return Boolean
     */
    public boolean remove(E element) {
        int index = indexOf(element);
        return index == -1 ?
                false : element.equals(remove(index));
    }

    /**
     * 向列表指定位置插入一个新的元素。
     * @param index
     * @param element
     * @return Previous element
     * @throws IndexOutOfBoundsException
     */
    public E insert(int index, E element)
            throws IndexOutOfBoundsException {
        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException();
        }
        index -= 1;
        Node<E> prev = head;
        while (index >= 0) {
            prev = prev.getNext();
            --index;
        }
        Node<E> current = prev.getNext();
        Node<E> node = new Node<E>(element, null);
        node.setNext(current);
        prev.setNext(node);
        return current == null ? null : current.getElem();
    }

    /**
     * 清空链表。
     * @Param []
     * @return void
     */
    public void clear() {
        while (head != null) {
            Node<E> n = head;
            head = head.getNext();
            n.setElem(null);
            n.setNext(null);
        }
        head = new Node<E>();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (Node<E> current = head.getNext();
             current != null;
             current = current.getNext()) {
            sb.append(current.getElem().toString());
            sb.append(", ");
        }
        sb.append(']');
        return sb.toString();
    }
}

分析完了整个流程，先来推导一遍单向链表的结点Node

数据域
指针域
构造方法
无参构造方法
getter & setter

在双向链表的DLNode里面还多一个内容就是多了一个向前的指针域。

下面是单向链表的详细分析

class Node<E> {
    /**
     * 数据域
     */
    private E elem;
    /**
     * 指针域
     */
    private Node<E> next;
    /**
     * 构造方法
     */
    public Node(E element, Node<E> next) {
        this.elem = element;
        this.next = next;
    }
    /**
     * 无参构造方法
     */
    public Node() {
        this(null, null);
    }
    /* Setter & Getter */
    public void setElem(E element) {
        this.elem = element;
    }
    public E getElem() {
        return this.elem;
    }
    public void setNext(Node<E> next) {
        this.next = next;
    }
    public Node<E> getNext() {
        return this.next;
    }
}

代码清单：单链表节点（Node）

我们考虑单链表数据结构：单链表包含一枚头节点（Head），头结点不存储数据，而是指向第一个实际存储数据的节点；尾节点可以被定义为指针域为null的最后一枚节点。

单链表的构造方法即为单链表初始化：构造一枚数据域和指针域均为空的头节点。

public class SingleLinkedList<E> {
    /**
     * 链表头节点
     */
    private Node<E> head;
    /**
     * 构造方法：创建空链表
     * @param void
     */
    public SingleLinkedList() {
        this.head = new Node<E>();
    }
}

代码清单：单链表（Single Linked List）结构

单链表addFirst()方法向链表头部添加一个新的元素，插入的新元素总是位于链表头部（头节点指向的节点），这种插入元素的方式称为头插法，通过以下3步，即可完成向链表头部插入元素。

根据新元素构建一枚新节点
将新节点指针域置为头节点指向的节点
头节点指向新节点

...
    /**
     * 向链表头部添加一个新的元素（头插法）。
     * @param element
     * @return void
     */
    public void addFirst(E element) {
        Node<E> node = new Node<E>(element, null);
        node.setNext(head.getNext());
        head.setNext(node);
    }
...

代码清单：单链表addFirst()头插法

单链表addLast()方法向链表尾部添加一个新的元素，插入的新元素总是位于链表尾部（指针域为空的尾节点），这种插入元素的方式称为尾插法，通过以下4步，即可完成向链表尾部插入元素。

根据新元素构建一枚新节点
将新节点指针域置空
遍历链表找到尾节点（指针域为空的节点）
尾节点指向新节点

...
    /**
     * 向链表尾部添加一个新的元素（尾插法）。
     * @param element
     * @return void
     */
    public void addLast(E element) {
        Node<E> node = new Node<E>(element, null);
        Node<E> tail = head;
        while (tail.getNext() != null) {
            tail = tail.getNext();
        }
        tail.setNext(node);
    }
...

代码清单：单链表addLast()尾插法

理解了addFirst()与addLast()方法实现后，实现getFirst()与getLast()方法就非常简单了，返回头/尾节点数据域中存储的数据即可，但是需要考虑到链表为空的情况：直接抛出NoSuchElementException异常。

...
    /**
     * 取得链表头部第一个元素，链表为空则抛出异常。
     * @param void
     * @return First element of {@code LinkedList}.
     * @throws NoSuchElementException if this {@code LinkedList} is empty.
     */
    public E getFirst() throws NoSuchElementException {
        if (head.getNext() == null) {
            throw new NoSuchElementException();
        }
        return head.getNext().getElem();
    }
    /**
     * 取得链表尾部最后一个元素，链表为空则抛出异常。
     * @param void
     * @return Last element of {@code LinkedList}.
     * @throws NoSuchElementException if this {@code LinkedList} is empty.
     */
    public E getLast() throws NoSuchElementException {
        Node<E> tail = head;
        while (tail.getNext() != null) {
            tail = tail.getNext();
        }
        if (tail == head) {
            throw new NoSuchElementException();
        }
        return tail.getElem();
    }
...

代码清单：单链表getFirst()与getLast()方法实现

上述实现代码段其实已经涉及到了isEmpty()与size()接口方法，现在我们来实现这两个方法。

size()：遍历链表元素并计数，计算链表存储元素数量。
isEmpty()：判断链表是否为空，可以借用size()方法（链表存储元素数量为0则表示链表为空），也可以直接判断头结点指针域是否为空。

...
    /**
     * 计算链表存储元素数量。
     * @param void
     * @return Size of elements in {@code LinkedList}.
     */
    public int size() {
        int cnt = 0;
        for (Node<E> n = head; n.getNext() != null; n = n.getNext()) {
            ++cnt;
        }
        return cnt;
    }
    /**
     * 检查链表是否为空。
     * @param void
     * @return Boolean {@code true} or {@code false}.
     */
    public boolean isEmpty() {
        return head.getNext() == null ? true : false;
    }
    /**
     * 检查链表是否为空。
     * @param void
     * @return Boolean {@code true} or {@code false}.
     */
    public boolean _isEmpty() {
        return this.size() > 0 ? false : true;
    }
...

代码清单：单链表isEmpty()与size()方法实现

单链表removeFirst()方法返回并移除链表第一个元素，通过以下步骤完成。

检查链表是否为空
获取链表首元素节点
头节点指向第二元素节点（首元素节点的下一个节点）
返回首元素节点数据域

...
    /**
     * 返回并移除链表头部第一个元素。
     * @param void
     * @return First element of this {@code Linked List}.
     * @throws NoSuchElementException
     */
    public E removeFirst() throws NoSuchElementException {
        if (this.isEmpty()) {
            throw new NoSuchElementException();
        }
        Node<E> first = head.getNext();
        head.setNext(
            first.getNext()
        );
        return first.getElem();
    }
...

代码清单：单链表removeFirst()方法实现

单链表removeLast()方法返回并移除链表最后一个元素，通过以下步骤完成。

检查链表是否为空
获取链表倒数第二元素节点（尾元素前一节点）
获取链表尾元素节点
将链表倒数第二元素节点指针域置空
返回尾元素节点数据域

...
    /**
     * 返回并移除链表尾部最后一个元素。
     * @param void
     * @return Last element of this {@code Linked List}.
     * @throws NoSuchElementException
     */
    public E removeLast() throws NoSuchElementException {
        if (this.isEmpty()) {
            throw new NoSuchElementException();
        }
        Node<E> prev = head;
        while (prev.getNext().getNext() != null) {
            prev = prev.getNext();
        }
        Node<E> last = prev.getNext();
        prev.setNext(null);
        return last.getElem();
    }
...

代码清单：单链表removeLast()方法实现

我们来考虑单链表的contains(E e)方法，检查链表中是否包含指定元素。我们使用equals()比较方法判断两个元素是否相等，因此，存入链表的数据类型必须实现equals()比较方法。

contains(E e)方法具体实现为：遍历链表，比较每个元素，找到即返回true，找不到则返回false。

...
    /**
     * 检查链表中是否包含目标元素，
     * 元素相等使用 {@code o.equals(obj)} 判断。
     * @param element
     * @return Boolean
     */
    public boolean contains(E element) {
        for (Node<E> current = head.getNext();
            current != null;
            current = current.getNext()) {
            if (element.equals(current.getElem())) {
                return true;
            }
        }
        return false;
    }
...

代码清单：单链表contains()方法实现

链表使用链式存储结构，存储的数据在内存空间中不连续，不能做到像数组一般高效的直接随即访问。我们来实现indexOf(E e)方法，返回指定元素所在链表的索引，元素不存在则返回-1，若存在多个相同元素，则返回第一次出现的索引。注意，我们将链表索引下标从0计起，与数组保持一致。indexOf()方法实现与contains()方法相似，加入一枚索引下标计数器即可。

...
    /**
     * 返回指定元素所在链表的索引。
     * @param element
     * @return The index of element in {@code LinkedList},
     *  return {@code -1} if element does not found.
     */
    public int indexOf(E element) {
        int index = 0;
        for (Node<E> current = head.getNext();
            current != null;
            current = current.getNext()) {
                if (element.equals(current.getElem())) {
                    return index;
                }
                ++index;
        }
        return -1;
    }
...

代码清单：单链表indexOf()方法实现

我们使用get(int index)方法获取链表中指定索引的元素，如果索引越界，抛出IndexOutOfBoundsException异常。

...
    /**
     * 获取链表指定索引的元素。
     * @param index
     * @return element
     * @throws IndexOutOfBoundsException
     */
    public E get(int index) throws IndexOutOfBoundsException {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> n = head.getNext();
        while (index > 0) {
            n = n.getNext();
            --index;
        }
        return n.getElem();
    }
...

代码清单：单链表get()方法实现

我们使用set(int index, E element)方法为链表中指定索引位置的元素设新值，如果索引越界，抛出IndexOutOfBoundsException异常。

...
    /**
     * 为链表指定索引位置的元素设新值。
     * @param index
     * @param element
     * @return Previous element in the index.
     * @throws IndexOutOfBoundsException
     */
    public E set(int index, E element) throws IndexOutOfBoundsException {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> n = head.getNext();
        while (index > 0) {
            n = n.getNext();
            --index;
        }
        E oldValue = n.getElem();
        n.setElem(element);
        return oldValue;
    }
...

代码清单：单链表set()方法实现

我们使用remove(int index)方法移除链表中指定索引下标位置的元素，具体步骤如下。如果索引下标越界，则抛出IndexOutOfBoundsException异常。

找到链表中指定索引下标的待移除节点及其前驱、后继节点
将指定索引下标节点的前后节点使用指针连接起来
返回移除节点数据域

...
    /**
     * 移除链表指定索引下标元素。
     * @param index
     * @return Removed element
     * @throws IndexOutOfBoundsException
     */
    public E remove(int index) throws IndexOutOfBoundsException {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
        index -= 1;
        Node<E> prev = head;
        while (index >= 0) {
            prev = prev.getNext();
            --index;
        }
        Node<E> current = prev.getNext();
        Node<E> next = current.getNext();
        prev.setNext(next);
        return current.getElem();
    }
...

代码清单：单链表remove(int index)方法实现

移除元素remove()方法还有另一种形式：boolean remove(E element)，移除链表中的指定元素。我们可以使用indexOf(E element)配合remove(int index)实现，先获取指定元素在链表中的索引下标，再移除掉，操作成功返回true，如果不存在目标元素，则返回false。

...
    /**
     * 移除链表指定元素，
     * 操作成功返回{@code true}，不存在目标元素则返回{@code false}。
     * @param element
     * @return Boolean
     */
    public boolean remove(E element) {
        int index = indexOf(element);
        return index == -1 ?
        false : element.equals(remove(index));
    }
...

代码清单：单链表remove(E element)方法实现

链表数据结构的优势在于其插入元素的开销比起数组要小很多，我们来实现链表插入元素insert()方法，具体步骤如下所示。如果索引下标越界，则抛出IndexOutOfBoundsException异常。

找到链表中指定索引下标节点（当前节点）及其前驱节点
创建一枚新节点
新节点指向当前节点
前驱节点指向新节点
返回当前节点数据域

...
    /**
     * 向列表指定位置插入一个新的元素。
     * @param index
     * @param element
     * @return Previous element
     * @throws IndexOutOfBoundsException
     */
    public E insert(int index, E element)
    throws IndexOutOfBoundsException {
        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException();
        }
        index -= 1;
        Node<E> prev = head;
        while (index >= 0) {
            prev = prev.getNext();
            --index;
        }
        Node<E> current = prev.getNext();
        Node<E> node = new Node<E>(element, null);
        node.setNext(current);
        prev.setNext(node);
        return current == null ? null : current.getElem();
    }
...

代码清单：单链表insert()方法实现

我们为链表提供一枚clear()方法，用于清空链表元素。由于 Java 语言的自动垃圾回收机制，直接将头节点（Head）置空即可表示清空链表，不用担心内存泄露问题，但是为了帮助垃圾收集器更好地做内存回收工作，这里我们选择显式清空每一个节点。

...
    /**
     * 清空链表。
     * @param void
     * @return void
     */
    public void clear() {
        while (head != null) {
            Node<E> n = head;
            head = head.getNext();
            n.setElem(null);
            n.setNext(null);
        }
        head = new Node<E>();
    }
...

代码清单：单链表clear()方法实现

最后，我们来覆写链表toString()方法，更加方便地查看链表元素。

...
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (Node<E> current = head.getNext();
            current != null;
            current = current.getNext()) {
                sb.append(current.getElem().toString());
                sb.append(", ");
        }
        sb.append(']');
        return sb.toString();
    }
...

代码清单：单链表toString()方法实现

双向链表（Double Linked List）


import java.lang.IndexOutOfBoundsException;
import java.util.NoSuchElementException;

/**
 * @program: draft
 * @description: 双向链表
 * @author: Fly.Hugh
 * @create: 2020-07-22 23:46
 **/
public class DoubleLinkedList<E> {
    /**
     * 链表头节点
     */
    private DLNode<E> head;
    /**
     * 链表尾节点
     */
    private DLNode<E> tail;
    /**
     * 构造方法：创建空链表
     * @Param []
     */
    public DoubleLinkedList() {
        this.head = new DLNode<E>();
        this.tail = new DLNode<E>();
        head.setNext(tail);
        tail.setPrev(head);
    }

    /**
     * 向双向链表指定索引位置插入一个新元素。
     * @param index
     * @param element
     * @return Previous element
     * @throws IndexOutOfBoundsException
     */
    public E insert(int index, E element)
            throws IndexOutOfBoundsException {
        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException();
        }
        DLNode<E> current = head;
        while (index >= 0) {
            current = current.getNext();
            --index;
        }
        DLNode<E> node = new DLNode<E>(element, null, null);
        node.setNext(current);
        node.setPrev(current.getPrev());
        current.getPrev().setNext(node);
        current.setPrev(node);;
        return current.getNext() == null ? null : current.getElem();
    }
    /**
     * 移除双向链表指定元素，
     * 操作成功返回{@code true}，不存在目标元素则返回{@code false}。
     * @param element
     * @return Boolean
     */
    public boolean remove(E element) {
        int index = indexOf(element);
        return index == -1 ?
                false : element.equals(remove(index));
    }
    /**
     * 移除双向链表指定索引下标元素。
     * @param index
     * @return Removed element
     * @throws IndexOutOfBoundsException
     */
    public E remove(int index) throws IndexOutOfBoundsException {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
        /* Input: 1 */
        /* head <--> elem(1) <--> elem(2) <--> elem(3) <--> tail */
        DLNode<E> node = head.getNext();
        while (index > 0) {
            node = node.getNext();
            --index;
        }
        node.getPrev().setNext(node.getNext());
        node.getNext().setPrev(node.getPrev());
        node.setPrev(null);
        node.setNext(null);
        return node.getElem();
    }
    /**
     * 为双向链表指定索引位置的元素设新值。
     * @param index
     * @param element
     * @return Previous element in the index.
     * @throws IndexOutOfBoundsException
     */
    public E set(int index, E element) throws IndexOutOfBoundsException {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
        DLNode<E> node = head.getNext();
        while (index > 0) {
            node = node.getNext();
            --index;
        }
        E oldElem = node.getElem();
        node.setElem(element);
        return oldElem;
    }
    /**
     * 获取双向链表指定索引位置的元素。
     * @param index
     * @return element
     * @throws IndexOutOfBoundsException
     */
    public E get(int index) throws IndexOutOfBoundsException {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
        DLNode<E> node = head.getNext();
        while (index > 0) {
            node = node.getNext();
            --index;
        }
        return node.getElem();
    }
    /**
     * 返回指定元素所在双向链表的索引位置。
     * @param element
     * @return The index of element in {@code DoubleLinkedList},
     * return {@code -1} if element does not found.
     */
    public int indexOf(E element) {
        int index = 0;
        for (DLNode<E> current = head.getNext();
             current.getNext() != null;
             current = current.getNext()) {
            if (element.equals(current.getElem())) {
                return index;
            }
            ++index;
        }
        return -1;
    }
    /**
     * 检查双向链表中是否包含目标元素，
     * 元素相等使用 {@code o.equals(obj)} 判断。
     * @param element
     * @return Boolean
     */
    public boolean contains(E element) {
        for (DLNode<E> current = head.getNext();
             current.getNext() != null;
             current = current.getNext()) {
            if (element.equals(current.getElem())) {
                return true;
            }
        }
        return false;
    }
    /**
     * 移除并返回双向链表尾部最后一个元素。
     * @Param []
     * @return Last element of this {@code DoubleLinkedList}.
     * @throws NoSuchElementException
     */
    public E removeLast() throws NoSuchElementException {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        DLNode<E> node = tail.getPrev();
        node.getPrev().setNext(tail);
        tail.setPrev(node.getPrev());
        node.setPrev(null);
        node.setNext(null);
        return node.getElem();
    }
    /**
     * 移除并返回双向链表头部第一个元素。
     * @Param []
     * @return First element of this {@code DoubleLinkedList}.
     * @throws NoSuchElementException
     */
    public E removeFirst() throws NoSuchElementException {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        DLNode<E> node = head.getNext();
        node.getNext().setPrev(head);
        head.setNext(node.getNext());
        node.setPrev(null);
        node.setNext(null);
        return node.getElem();
    }
    /**
     * 向双向链表头部添加一个新元素。
     * @param element
     * @return void
     */
    public void addFirst(E element) {
        DLNode<E> node = new DLNode<E>(element, null, null);
        node.setPrev(head);
        node.setNext(
                head.getNext()
        );
        head.setNext(node);
        head.getNext().setPrev(node);
    }
    /**
     * 向双端链表尾部添加一个新元素。
     * @param element
     * @return void
     */
    public void addLast(E element) {
        DLNode<E> node = new DLNode<E>(element, null, null);
        node.setPrev(tail.getPrev());
        node.setNext(tail);
        tail.getPrev().setNext(node);
        tail.setPrev(node);
    }
    /**
     * 取得双向链表头部第一个元素，链表为空则抛出异常。
     * @Param []
     * @return First element of {@code DoubleLinkedList}.
     * @throws NoSuchElementException
     */
    public E getFirst() throws NoSuchElementException {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return head.getNext().getElem();
    }
    /**
     * 取得双向链表尾部最后一个元素，链表为空则抛出异常。
     * @Param []
     * @return Last element of {@code DoubleLinkedList}.
     * @throws NoSuchElementException
     */
    public E getLast() throws NoSuchElementException {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return tail.getPrev().getElem();
    }
    /**
     * 计算双向链表存储元素数量。
     * @Param []
     * @return Size of {@code DoubleLinkedList}.
     */
    public int size() {
        int cnt = 0;
        for (DLNode<E> n = head.getNext();
             n.getNext() != null;
             n = n.getNext()) {
            ++cnt;
        }
        return cnt;
    }
    /**
     * 检查双向链表是否为空。
     * @Param []
     * @return Boolean {@code true} or {@code false}.
     */
    public boolean isEmpty() {
        return this.size() > 0 ? false : true;
    }
    /**
     * 清空双向链表。
     * @Param []
     * @return void
     */
    public void clear() {
        while (head.getNext() != null) {
            DLNode<E> current = head;
            head = head.getNext();
            current.setElem(null);
            current.setPrev(null);
            current.setNext(null);
        }
        head = new DLNode<E>();
        tail = new DLNode<E>();
        head.setNext(tail);
        tail.setPrev(head);
    }
    /**
     * 返回双向链表字符串形式。
     * @Param []
     * @return void
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (DLNode<E> current = head.getNext();
             current.getNext() != null;
             current = current.getNext()) {
            sb.append(current.getElem().toString());
            sb.append(", ");
        }
        sb.append(']');
        return sb.toString();
    }
}

找出两个链表的交点

Intersection of Two Linked Lists (Easy)

Leetcode / 力扣

例如以下示例中 A 和 B 两个链表相交于 c1：

A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗
B:    b1 → b2 → b3

但是不会出现以下相交的情况，因为每个节点只有一个 next 指针，也就只能有一个后继节点，而以下示例中节点 c 有两个后继节点。

A:          a1 → a2       d1 → d2
                    ↘  ↗
                      c
                    ↗  ↘
B:    b1 → b2 → b3        e1 → e2

要求时间复杂度为 O(N)，空间复杂度为 O(1)。如果不存在交点则返回 null。

设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。

给出来的标准答案：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode l1 = headA, l2 = headB;
    while (l1 != l2) {
        l1 = (l1 == null) ? headB : l1.next;
        l2 = (l2 == null) ? headA : l2.next;
    }
    return l1;
}

这个代码只能跑一跑基本类型的链表，真正要运行的话还有一些坑要踩

当Node泛型是String的时候

private static Node getIntersectionNode(Node headA, Node headB) {
    Node l1 = headA, l2 = headB;

    while (l1.getElem() != l2.getElem()) {
        l1 = (l1 == null) ? headB : l1.getNext();
        l2 = (l2 == null) ? headA : l2.getNext();
    }
    return l1;
}

这样的代码是可以通过的，但是这是特例，因为

equals不Override的情况下总是调用==，==在基本数据类型里面是比较值，在别的类型里面是比较内存地址，复写的情况下会调用equals方法，String类型不是基本数据类型，但是使用String a=”a”的时候，默认使用的不是堆内存，使用的常量池，所以使用 == 会判定true，使用new的话会使用堆内存所以判定false

举例一个普通的pojo类，需要实现一些方法

/**
 * @program: draft
 * @description: java pojo
 * @author: Fly.Hugh
 * @create: 2020-07-24 23:05
 **/
public class Person {

    private String name;

    public Person(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Person person = (Person) o;

        return getName().equals(person.getName());
    }

    @Override
    public int hashCode() {
        return getName().hashCode();
    }
}

然后

private static Node getIntersectionNode(Node<Person> headA, Node<Person> headB) {
    Node<Person> l1 = headA, l2 = headB;
    Person NULL = new Person("NULL");
    Node<Person> l3 = new Node<Person>(NULL,headA);

    while (!(l1.getElem().equals(l2.getElem()))) {

        l1 = (l1 == l3) ? headB : l1.getNext();
        if (l1 == null) l1 = l3;

        l2 = (l2 == null) ? headA : l2.getNext();
        if (l2 == null) l2 = l3;
    }

    return l1;
}

其中引入了一个l3，引入的原因是如果两个链表不一样长的时候会出现某个链表先遍历完毕，然后这个时候null.getElem()就会报错。

这个问题有个变种，就是判断两个链表是否存在交点，直接判断LinkedListA和LinkedListB两个链表最后一个Node元素是否相等即可。

解到这里，我突然感觉我走偏了，我这里链表相同的条件出了点问题，可能要判断的其实是Node是否相同而已，直接判断地址即可。

也就是说第一段代码，没有问题。

我仅仅通过addLast是没有办法创建出两个有用相同节点的链表的，如果要模拟那种链表的话，需要三个链表，把第一个链表的Last节点的指针指向第三个链表的头结点即可。造成这种乌龙的原因是因为对一些底层的概念忘得差不多了。

这题同时还有一个变种就是是否存在交点。

如果仅仅问是否存在交点的话，最简单的办法就是直接把两个链表的最后一个节点分别拿出来判断，如果两个节点相等（地址相等）的话，和存在交点是互为充要条件的。

其实解法很多，有一种取巧解法先把两个链表的size拿出来，因为是有公共部分的，公共部分的长度肯定相等，于是乎把长的链表多出来的那个部分忽略，假设长链表的size是m，短链表的size是n，m-n得到多出来的部分，长链表从m-n+1的位置开始，锻炼表从head位置开始，在同一个循环里面遍历，如果两者相等了，那么就说明有交点。

有一种经典的解法可以把这个问题转化一下，把链表alist的尾节点挂到blist的头节点上面，于是问题变成了探究blist是否存在环，如果存在的话，就说明两个链表存在着交点。

这里前面两种都相对简单，仅仅探讨第三种情况。

使用两个指针从头节点开始遍历，一个速度是1，一个速度是2，如果链表存在环的，那么速度块的指针总是会给速度慢的套圈。

public static boolean judgeIfTheIntersectionExists(Node head) {

    Node slow = head;
    Node fast = head;

    while(fast!=null && fast.getNext() != null){
        slow = slow.getNext();
        fast = fast.getNext().getNext();

        if(slow == fast) return true;
    }

    return false;
}

如此，即可。

反转链表

反转链表介绍两种办法，一种是递归，一种是头插入法。


import com.hugh.datastructure.LinkedListUtils;
import com.hugh.datastructure.dllist.DLNode;
import com.hugh.datastructure.dllist.MyDoubleLinkedList;
import com.hugh.datastructure.linkedlist.MySingleLinkedList;
import com.hugh.datastructure.linkedlist.Node;
import com.hugh.datastructure.linkedlist.pojo.Person;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

/**
 * @Author Fly.Hugh
 * @Date 2020/7/25 17:53
 * @Version 1.0
 **/
public class ReverseLinkedList {

    private static Logger logger = LogManager.getLogger(ReverseLinkedList.class.getName());

    public static void main(String[] args) {

        MySingleLinkedList list = LinkedListUtils.generateSingleLinkList(1, 2, 3, 4, 5, 6, 7, 8, 9);

        System.out.println(list);

        Node node = reverseList(list.getFirst());

        /**
         * 因为整个链表已经反转，所以只能根据新的头节点往下便利出新的节点。
         */
        while (node != null) {
            System.out.println(node.getElem());
            node = node.getNext();
        }
    }

    /**
     *
     * @return com.hugh.datastructure.linkedlist.Node
     * @author Fly.Hugh
     * @Description 递归反转列表 head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
     * 变为  head -> 1 <- 2 <- 3 <- 4 <- 5 <- 6 <- 7 <- 8 <- 9  可以因为我的链表设计了null的head 所以导致了反转之后使用原先输出方式就不正确了
     * @Date 16:35 2020/7/26
     * @Param [head]
     **/
    public static Node reverseList(Node head) {
        logger.info("step1:" + head + " " + head.getElem());
        if (head == null || head.getNext() == null) {
            return head;
        }

        Node next = head.getNext();
        Node newhead = reverseList(next);
        /**
         * 这里的 newhead 的赋值过程，在head = 9的时候，作为head Node类型返回
         * 返回是9之后，这个9在每一次递归的过程中都在传递，因为不涉及newhead元素的再次赋值，只是简单的值传递，
         * 所以一直到最后返回的都是9，也就是头节点。
         * */
        logger.info("newhead:" + newhead + " " + newhead.getElem());
        next.setNext(head);
        head.setNext(null);

        return newhead;
    }

    /**
     * 头插法，
     * 从第一个值开始改变，有三个指针，pre指针，next指针，head也就是cur指针，每次循环改变pre和next的值，
     * pre 和 next 分别记录上一个迭代和下一个迭代head的值
     * @param head
     * @return
     */
    public static Node reverseIterativeltly(Node head) {
        Node pre = null;
        Node next = null;
        while (head != null) {
            /**
             * 1.为next赋值
             */
            next = head.getNext();
            /**
             * 2.pre指针每次使用的值都是延迟一个迭代，所以先使用再赋值
             */
            head.setNext(pre);
            /**
             * 3.为pre赋新值进入下一个轮回
             */
            pre = head;
            /**
             * 4.head指针重新赋值
             */
            head = next;
        }
        return pre;
    }
}

归并两个有序的链表


import com.hugh.datastructure.LinkedListUtils;
import com.hugh.datastructure.linkedlist.MySingleLinkedList;
import com.hugh.datastructure.linkedlist.Node;
import com.hugh.datastructure.linkedlist.SingleLinkedList;

/**
 * @Author Fly.Hugh
 * @Date 2020/7/27 5:40 下午
 * @Version 1.0
 **/
public class MergeTwoSortedLists {
    public static void main(String[] args) {
        MySingleLinkedList<Integer> listA = LinkedListUtils.generateSingleLinkList(2, 4, 6, 7, 10, 13, 15, 17, 20);
        MySingleLinkedList<Integer> listB = LinkedListUtils.generateSingleLinkList(1, 3, 5, 7, 100);
        Node node = mergeTwoLists(listA.getFirst(), listB.getFirst());
        while (node != null) {
            System.out.println(node.getElem());
            node = node.getNext();
        }
    }

    /**
     * 归并两个有序的链表，
     * 继续使用递归的方法，非常优雅的代码
     * 要适应使用递归的方法，就要适应一个自下而上的思维。
     * 此情况下，通过递归先找到最大的值，然后每次回溯上一个节点的时候都有两个选项，所以代码最终变成了这个样子
     */
    private static Node mergeTwoLists(Node<Integer> l1, Node<Integer> l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.getElem() <= l2.getElem()) {
            l1.setNext(mergeTwoLists(l1.getNext(),l2));
            return l1;
        } else {
            l2.setNext(mergeTwoLists(l1,l2.getNext()));
            return l2;
        }
    }
}

从有序链表中删除重复节点

private static Node<Integer> deleteDuplicatesThird(Node<Integer> head) {
    if (head == null || head.getNext() == null) return head;

    head.setNext(deleteDuplicatesThird(head.getNext()));

    /**
    * @author Fly.Hugh
    * @Description 根据递归三问
     * 第一问 终止条件是什么
     * 第二问 本级递归需要做什么
     * 第三问 返回值是什么
     * 本题目中，根据递归三问，追溯到链表的最后，首先拿到了最后一个值
     * 这个值跟前面一个值进行对比，如果相等话，应该返还哪一个呢？
     * 肯定是返回后面一个的。
     * 原因是我们设置的返回值同时设置了前面一个链表的next
     * 如果我们返回第一个的话，等同于没有进行去重操作。
     * 如果返回第二个的话等于把倒数第三个的next设置在了最后一个上面。
     * 这样才是符合逻辑的。
    * @Date 4:17 2020/7/31
    * @Param [head]
    * @return com.hugh.datastructure.linkedlist.Node<java.lang.Integer>
    **/
    return (head.getElem() == head.getNext().getElem()) ? head.getNext() : head;
}

删除链表的倒数第 n 个节点


    /**
     * 汗颜，想起我做的第一道题目，求两链表交点的那题，当时那题，我引入了一个L3节点
     * 因为两个链表长度不一样的时候，先遍历完毕的那个链表会出现一个Null.getElement的空指针问题，
     * 我他妈研究了好久，引入了一个L3，因为没有总结，在这道题目用例是[1] 1的时候出现的空指针又卡了好久。
     * @param head
     * @param n
     * @return
     */
    private static Node<Integer> removeNthNodeFromEndOfList(Node<Integer> head, int n) {
        Node<Integer> pre = new Node<>();
        pre.setNext(head);
        //双指针
        Node<Integer> slow = pre;
        Node<Integer> fast = pre;

/*        for (int i = 0; i < n; i++) {
            fast = fast.getNext();
        }*/

        // 另一种写法
        while(n != 0){
            fast = fast.getNext();
            n--;
        }

        while(fast.getNext() != null) {
            fast = fast.getNext();
            slow = slow.getNext();
        }

        slow.setNext(slow.getNext().getNext());

        return  pre.getNext();
    }

交换链表中的相邻结点


/**
 * 第一次自己写这个迭代法的时候，其实就完成得差不多了，但是没有加一把劲解出来，有点可惜，一道medium的题目
 * 这个解法引入了多个变量
 * 首先要弄清楚一个东西，不能因为变量变多了人就开始晕了
 * 首先定义了三个指针变量，然后考虑到将来要返回头节点，所以这边还多了一个node是为了将来要返回的，也就是四个变量，再加上一个head变量
 * 除了变量多了点，别的都没啥，有手就行。
 * @param head
 * @return
 */
private static Node swapPairsIteration(Node head) {
    Node dummy = new Node();
    dummy.setNext(head);

    Node pre = dummy;

    Node first = null;
    Node second = null;

    while(head != null && head.getNext() != null) {
        first = head;
        second = head.getNext();

        pre.setNext(second);
        first.setNext(second.getNext());
        second.setNext(first);

        pre = first;
        head = first.getNext();
    }
    return dummy.getNext();
}

/**
 * 其实拿到这个题目，我就在想能不能用递归做了。
 * 感觉没有什么好的思路。
 * 三板斧
 *      整个递归的终止条件。
 *      一级递归需要做什么？
 *      应该返回给上一级的返回值是什么？
 * 返回值应该是偶数位置的值？
 * 递归终止条件还是比较常规的。
 *
 * @param head
 * @return
 */
private static Node swapPairsRecursion(Node head) {
    if(head == null || head.getNext() == null) {
        return head;
    }

    Node odd = head;
    Node even = head.getNext();

    odd.setNext(swapPairsRecursion(even.getNext()));
    even.setNext(odd);

    return even;
}

链表求和

package com.hugh.datastructure.linkedlist.leecode;

import com.hugh.datastructure.LinkedListUtils;
import com.hugh.datastructure.linkedlist.MySingleLinkedList;
import com.hugh.datastructure.linkedlist.Node;

import java.util.Stack;

/**
 * @Author Fly.Hugh
 * @Date 2020/8/5 15:29
 * @Version 1.0
 **/
public class AddTwoNumbers {
    public static void main(String[] args) {
        MySingleLinkedList listA = LinkedListUtils.generateSingleLinkList(7,2,4,3);
        MySingleLinkedList listB = LinkedListUtils.generateSingleLinkList(5,4,6);
//        Node node = addTwoNumbersMedium(listA.getFirst(), listB.getFirst());
        Node node = addTwoNumbersEasy(listA.getFirst(), listB.getFirst());
        LinkedListUtils.traverseLinkListFromFirst(node);
    }

    /**
     * 说实话 我只想用递归来做这题
     * 但是递归并没有很好地办法来解决这个问题。
     * 这个问题里面引入了Java6 开始使用的Stack，stack可以作为一个新的知识点存入我的leeocode框架。
     *
     * @param headA
     * @param headB
     * @return
     */
    private static Node addTwoNumbersMedium(Node<Integer> headA, Node<Integer> headB) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();

        while (headA != null) {
            s1.push(headA.getElem());
            headA = headA.getNext();
        }

        while (headB != null) {
            s2.push(headB.getElem());
            headB = headB.getNext();
        }

        Node res = null;
        int c = 0;
        while (!s1.isEmpty() || !s2.isEmpty() || c > 0) {
            int sum = (s1.isEmpty() ? 0 : s1.pop()) + (s2.isEmpty() ? 0 : s2.pop()) + c;
            Node n = new Node(sum % 10, null);
            c = sum / 10;
            n.setNext(res);
            res = n;
        }

        return res;
    }

    /**
     * @return com.hugh.datastructure.linkedlist.Node
     * @author Fly.Hugh
     * @Description 这个情况要比上面的情况简单不少，少了一个过程，就是那个压栈 弹栈的过程。
     * @Date 21:37 2020/8/5
     * @Param [headA, headB]
     **/
    private static Node addTwoNumbersEasy(Node<Integer> headA, Node<Integer> headB) {
        Node nh = new Node(0, null);
        int c = 0;
        Node index = nh;

        while (headA != null || headB != null || c > 0) {
            int sum =
                    ((headA == null) ? 0 : headA.getElem()) +
                            ((headB == null) ? 0 : headB.getElem()) +
                            c;
            index.setNext(new Node(sum % 10, null));
            index = index.getNext();
            c = sum / 10;
            if (headA != null) headA = headA.getNext();
            if (headB != null) headB = headB.getNext();
        }
        if (c > 0) index.setNext(new Node(c, null));
        return nh.getNext();
    }
}

回文链表

package com.hugh.datastructure.linkedlist.leecode;

import com.hugh.datastructure.LinkedListUtils;
import com.hugh.datastructure.linkedlist.MySingleLinkedList;
import com.hugh.datastructure.linkedlist.Node;
import sun.awt.image.ImageWatched;

import java.util.ArrayList;

/**
 * @program: draft
 * @description: 回文链表
 * @author: Fly.Hugh
 * @create: 2020-08-06 03:35
 **/
public class isPalindrome {
    public static void main(String[] args) {
        MySingleLinkedList list = LinkedListUtils.generateSingleLinkList(1, 2, 3, 3, 2, 1, 4);
//        boolean flag = isPalindromeFirst(list.getFirst());

//        boolean flag = new isPalindrome().isPalindromeSecond(list.getFirst());

        boolean flag = new isPalindrome().isPalindromeThird(list.getFirst());
        System.out.println(flag);
        System.out.println(list);
/*
        MySingleLinkedList listRecursion = LinkedListUtils.generateSingleLinkList(1, 2, 3,4,5,6,7,8,9);
        Node<Integer> node = new isPalindrome().reverseList(listRecursion.getFirst());
        System.out.println(node.getElem());
        LinkedListUtils.traverseLinkListFromFirst(node);*/

    }

    /**
    * @author Fly.Hugh
    * @Description
     * 首先介绍一下回文词的意思: 正反看都一样的英文单词
     * 这里就是链表前后两个部分是呈轴对称。
     * 在LeeCode里面这道题目难度判定是Easy，可能是因为并没有强制指定这道题目的时间复杂度和空间复杂度。
     * 贴上三种典型一点的解法：
     *
     * First:将值复制到数组中后用双指针法
     * 数组列表(ArrayList) 底层是使用数组存储值，我们可以通过索引在 O(1) 的时间访问列表任何位置的值，这是由于内存寻址的方式。
     * 链表存储的是称为节点的对象，每个节点保存一个值和指向下一个节点的指针。访问某个特定索引的节点需要 O(n) 时间，因为要通过指针获取到下一个位置的节点。
     *
     * 定数组列表是否为回文很简单，我们可以使用双指针法来比较两端的元素，并向中间移动。一个指针从起点向中间移动，另一个指针从终点向中间移动。
     *
     * 这需要 O(n) 的时间，因为访问每个元素的时间是 O(1)，而有 n 个元素要访问。
     *
     * 直接在链表上操作并不简单，因为不论是正向访问还是反向访问都不是 O(1), 下面的两种方式演示了特意用递归来解决问题。
     * 而将链表的值复制到数组列表中是 O(n)，因此最简单的方法就是将链表的值复制到数组列表中，再使用双指针法判断。
     * 因此我们可以分为两个步骤：
     * 1.复制链表值到数组列表中。
     * 2.使用双指针法判断是否为回文。
    * @Date 3:36 2020/8/6
    * @Param [head]
    * @return boolean
    **/
    private static boolean isPalindromeFirst(Node head) {
        ArrayList arr = new ArrayList<>();

        while (head != null) { //这边的判断我一开始用的是head.getNext, 是错误的，最后一个值没法放入数组。
            arr.add(head.getElem());
            head = head.getNext();
        }

        int front = 0;
        int back = arr.size() - 1;
        while(front < back) {   // 我自己解的时候这里用的是 != ，在数据个数为基数的时候无法生效
            if(((int)arr.get(front)) != ((int)arr.get(back))) {
                return false;
            }
            front ++;
            back --;
        }

        return true;
    }

    // ==================== Second ====================>>>>>>>>>>>>>>>>>>>>>>>>>

    /**
    * @author Fly.Hugh
    * @Description
     * 考虑用递归
     * 既然是回文链表，从第一个节点开始往后遍历和递归到最后一个然后往前面递归，类似双指针，每组节点的值应该都是相等的。
     *
     * 这里关键问题就是：
     * 如何在递归的过程中同时控制两边的指针比较？
     *
     * 我想了半天没想到，
     * 看了答案，引入了一个外部变量，很巧妙，不过也就是这个外部变量把整个递归的空间复杂度从O(1)提升到了O(n).
     *
    * @Date 4:40 2020/8/6
    * @Param [head]
    * @return boolean
    **/
    private boolean isPalindromeSecond(Node head) {
        firstNode = head;
        return compare(head);
    }

    private Node firstNode;

    /**
     * 这个递归并不像我之前接触的递归，之前我接触的递归返回的返回值总是Node
     * 这里的递归返回值是bool类型
     *
     * 当某一层递归出现了return的时候并不代表了就会直接跳出循环。
     * 他会把返回值返回给上层
     *
     * 本体逻辑：
     * -- 如果在递归的过程中，一旦出现了某一层递归返回的是false，
     * 那么就要一直返回false到跳出递归，如果是true，则继续逻辑判断，
     * 某些角度上来讲，这个逻辑和if的逻辑正好相反。
     *                      if(!flag(next)) = false;        return true;
     * 这就是 bool型递归的真谛。
     * flag()就是函数本身，后面一级的函数返上来的bool就是最后return的true，
     *
     * @param head
     * @return
     */
    private boolean compare(Node<Integer> head){
        if (head != null) {
            if(!compare(head.getNext())) return false;
            if (head.getElem() != firstNode.getElem()) return false;
            firstNode = firstNode.getNext();
        }
        return true;
    }


    // <<<<<<<<<<<<<<<<<<<<<<<<<==================== Finish ====================

    // ==================== Third ====================>>>>>>>>>>>>>>>>>>>>>>>>>

    /**
    * @author Fly.Hugh
    * @Description
     * 第三种方案，为了实现空间复杂度O(n)
     * 才用了一种更加复杂一点的方案
     * 题解中此种解法分为了五个步骤
     * 1 找到前半部分链表的尾节点。
     * 2 反转后半部分链表。
     * 3 判断是否为回文。
     * 4 恢复链表。
     * 5 返回结果。
    * @Date 1:23 2020/8/7
    * @Param [head]
    * @return boolean
    **/
    private boolean isPalindromeThird(Node<Integer> head) {

        if (head == null) return true;              // 修正

        Node<Integer> firstHalfEnd  = endOfFirstHalf(head);
        Node<Integer> secondHalfStart  = reverseList_interpolation(firstHalfEnd.getNext());
        LinkedListUtils.traverseLinkListFromFirst(head);

        Node<Integer> index1 = head;
        Node<Integer> index2 = secondHalfStart;
        boolean flag = true;

        while(flag && index2 != null) {                       // 修正，我原先用的是 head.getNext() != null，就变成了比对最后一位的值。 再修正，一开始用的index1 != null 会报错。 index1 遍历比index2多一位，这里面index1 和index2存在交点。
            if(index1.getElem() != index2.getElem()) {
                flag = false;
            }
            index1 = index1.getNext();
            index2 = index2.getNext();
        }

        firstHalfEnd.setNext(reverseList_interpolation(secondHalfStart));     // 修正 牛逼 牛大逼，自己的函数用两次，第一次的结果套进去再运行一次把链表指针的顺序改过来。

        return flag;
    }

    /**
     * 首先要说明 我在这里使用递归肯定是错误的，因为反转链表的时候使用递归就导致了空间复杂度到达了O(n)，
     * 整体的空间复杂度必然不可能小于这个值。
     * 然后考虑功能，虽然递归能够做到翻转链表，
     * 但是并没有切断第一段链表最后一个节点指向第二段头节点这个指向，也就是从理论上来说，
     * 1 -> 2 -> 3 -> 3 -> 2 -> 1 变成了
     * 1 -> 2 -> 3 -> 3 <- 2 <- 1
     *
     * 这里的这个特性主要是对上面值判断的时候非空判断提出了要求。
     *
     * @param head
     * @return
     */
    private Node reverseList(Node head) {
        if(head == null || head.getNext() == null) {
            return head;
        }
        Node next = head.getNext();
        Node newhead = reverseList(next);
        next.setNext(head);
        head.setNext(null);

        return newhead;
    }

    /**
     * 这里还是使用头插法来更换指针,头插法可以把空间复杂度限制在 O(1)
     *
     * @param head
     * @return
     */
    private Node reverseList_interpolation(Node head) {
        Node pre = null;
        Node cur = head;
        while (cur != null) {
            Node next = cur.getNext();
            cur.setNext(pre);
            pre = cur;
            cur = next;
        }
        return pre;
    }

    private Node endOfFirstHalf(Node head) {
        /**
         * head有两种情况，
         * 当head是真的head节点的时候 两者都等于head可以实现模拟快慢指针，
         * 因为head是没有意义的，
         * 但是当head是first节点的时候 如果仍然用head的话，
         * 相当于slow和fast都走了相同距离的第一步 和我们预期不同
         * 所以fast用 head.Next 模拟了走两步
         * 任然符合我们对fast和slow的期待。
         */
        Node slow = head;
        Node fast = head.getNext();

        // fast.getNext() != null 理应放在前面
        while(fast.getNext() != null && fast.getNext().getNext() != null) {
            slow = slow.getNext();
            fast = fast.getNext().getNext();
        }
        return slow;
    }

    // <<<<<<<<<<<<<<<<<<<<<<<<<==================== Finish ====================
}

tips 之前的Code都是用我自己的用例写的，后面为了方便直接调试代码，我会使用LeeCode的用例。

分隔链表

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

示例 1：

输入:
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表，而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。
示例 2：

输入:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释:
输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。

提示:

root 的长度范围： [0, 1000].
输入的每个节点的大小范围：[0, 999].
k 的取值范围： [1, 50].

package com.hugh.datastructure.linkedlist.leecode.nativecode;

import com.hugh.datastructure.linkedlist.leecode.realex.ListNode;
import com.hugh.datastructure.linkedlist.leecode.realex.ListNodeUtils;

/**
 * @program: draft
 * @description: 回文链表
 * @author: Fly.Hugh
 * @create: 2020-08-08 21:27
 **/
public class IsPalindrome {
    public static void main(String[] args) {
        IsPalindrome isPalindrome = new IsPalindrome();

/*        System.out.println("====================对findEndOfHalf的校验====================");
        ListNode head = ListNodeUtils.generateLinkedList(1,2,3,4,5,6,7);
        ListNode slow = isPalindrom.findEndOfHalf(head);
        System.out.println(slow.val);
        System.out.println("========================================");*/

        ListNode head = ListNodeUtils.generateLinkedList(1,2,3,4,5);
        boolean palindrom = isPalindrome.isPalindrome(head);
        System.out.println(palindrom);

    }

    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }

        ListNode endOfHalf = findEndOfHalf(head);
        ListNode backHead = findBackHead(endOfHalf.next);

        ListNode index1 = head;
        ListNode index2 = backHead;
        Boolean flag = true;
        while(flag == true && index2 != null) {
            if(index1.val != index2.val) {
                flag = false;
            }
            index1 = index1.next;
            index2 = index2.next;
        }

        findBackHead(backHead);

        return flag;
    }

/*    private ListNode findBackHead(ListNode head) {
        if(head.next == null) {
            return head;
        }

        ListNode next = head.next;
        ListNode newHead = findBackHead(next);
        next.next = head;
        head.next = null;

        return newHead;
    }*/

    // 头插法反转列表
    private ListNode findBackHead(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }

        return pre;
    }

    private ListNode findEndOfHalf(ListNode head) {
        ListNode fast = head.next;
        ListNode slow = head;

        // 考虑奇数和偶数的情况
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }
}

奇偶链表

package com.hugh.datastructure.linkedlist.leecode.nativecode;

import com.hugh.datastructure.linkedlist.leecode.realex.ListNode;
import com.hugh.datastructure.linkedlist.leecode.realex.ListNodeUtils;

/**
 * @Author Fly.Hugh
 * @Date 2020/8/11 15:05
 * @Version 1.0
 **/
public class OddEvenLinkedList {
    public static void main(String[] args) {
        OddEvenLinkedList oddEvenLinkedList = new OddEvenLinkedList();

        ListNode node = ListNodeUtils.generateLinkedList(1,2,3,4,5,6,7,8);
        ListNode listNode = oddEvenLinkedList.oddEvenList(node);
        ListNodeUtils.traverseLinkListFromFirst(listNode);

    }

    /**
     * 要求：使用原地算法（一句话总结就是: 原地算法不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入的一种算法操作。）
     * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
     * <p>
     * 示例 1:
     * <p>
     * 输入: 1->2->3->4->5->NULL
     * 输出: 1->3->5->2->4->NULL
     * 示例 2:
     * <p>
     * 输入: 2->1->3->5->6->4->7->NULL
     * 输出: 2->3->6->7->1->5->4->NULL
     * <p>
     * 说明:
     * <p>
     * 应当保持奇数节点和偶数节点的相对顺序。
     * 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
     *
     * @param head
     * @return
     */
/*    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode odd = head;
        ListNode even = head.next;
        while (head != null) {
            ListNode next = head.next;
            pre.next = next;
            pre = head;
            head = head.next;
        }

        ListNode findOddLast = odd;
        while (findOddLast.next != null) {
            findOddLast = findOddLast.next;
        }

        findOddLast.next = even;

        return odd;
    }*/

    /**
    * @author Fly.Hugh
    * @Description 上面是我自己的写法，下面这种更巧妙一点，生了一个变量并且少了一次递归
    * @Date 20:47 2020/8/11
    * @Param [head]
    * @return com.hugh.datastructure.linkedlist.leecode.realex.ListNode
    **/
    public ListNode oddEvenList(ListNode head){
        // 特判：头结点为 null，返回null
        // head是奇链表的头
        if (head == null) return null;

        // odd是奇链表的当前节点，先初始化为head（初始化为奇链表头）
        ListNode odd  = head;
        // even是偶链表的当前节点，初始化为第二个节点也就是head.next
        ListNode even = head.next;
        // evenHead是偶链表的头节点，初始化为链表第二个节点（初始化为奇链表头的下一个节点）
        ListNode evenHead = even;

        while (even != null && even.next != null){
            // 这里while退出判断条件还是画图一下才能理解（也就是官方题解的STEP2）
            odd.next = even.next;  // 相当于odd.next = odd.next.next(跳过一个偶数节点)
            odd = odd.next;        // odd向前前进一位
            even.next = odd.next;   // 奇链表的下一个节点就是偶链表的节点
            even = even.next;       // even向前前进一位
        }
        // while条件结束，把偶链表头指针拼接到奇链表的最后
        odd.next = evenHead;
        // 返回奇链表头就是返回整个奇偶排序后的链表
        return head;
    }
}

注：后期用到的工具类，样例类，能直接在本地能够调试的LeeCode的代码环境在github可获取。

树

树（tree）是一种抽象数据类型（ADT），用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点通过连接它们的边组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树有很多种，向上面的一个节点有多余两个的子节点的树，称为多路树，后面会讲解2-3-4树和外部存储都是多路树的例子。而每个节点最多只能有两个子节点的一种形式称为二叉树。

节点：上图的圆圈，比如A,B,C等都是表示节点。节点一般代表一些实体，在java面向对象编程中，节点一般代表对象。

边：连接节点的线称为边，边表示节点的关联关系。一般从一个节点到另一个节点的唯一方法就是沿着一条顺着有边的道路前进。在Java当中通常表示引用。

根：树顶端的节点称为根。一棵树只有一个根，如果要把一个节点和边的集合称为树，那么从根到其他任何一个节点都必须有且只有一条路径。A是根节点。

父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点

子节点：一个节点含有的子树的根节点称为该节点的子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点；比如上图的D和E就互称为兄弟节点

叶节点：没有子节点的节点称为叶节点

子树：每个节点都可以作为子树的根，它和它所有的子节点、子节点的子节点等都包含在子树中。

节点的层次：从根开始定义，根为第一层，根的子节点为第二层，以此类推。

深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；

高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0

关于二叉树不成熟的一些理解

二叉树，本质上，是对链表和数组的一个折中（不成熟的说法，有说法是区块链）

链表和数组都是纯粹的数据结构，而二叉树就已经是分类器。

比如，我有一个任务，需要输入
10万个数据（32位整数），然后有两个操作：
1.添加(删除)一个整数。
2.询问第x大的数据。

比如，给出 1, 8, 13, 10（等等一堆数据）…….
然后询问第3大的数据，
然后插入 18
然后询问第4大的数据
再插入 9
再询问第2大的数据

不停的重复1,2
重复10万次。。

用有序链表，不行，查找（包括1需要找到对应位置，以及2查找）成本大O(N)，但具体这个插入操作成本小O(1)。
用有序数组，查找（2的查找）成本小O(1)。但1的插入操作成本很大O(N)。

所以，我们折中使用排序二叉树（二叉树仅仅作为排序二叉树的基础），查找（包括1需要找到对应位置，以及2查找）成本挺小O(logN)。具体这个插入操作成本也挺小O(logN)。

具体的应用就是由排序二叉树（由于普通排序二叉树可能会有不平衡的情况）引申出来的红黑树（linux中ext3文件系统管理），avl树“windows对进程地址空间的管理”。

二叉树工具类

前序、中序、后续遍历三种遍历方式都是DFS（深度优先遍历的三种方式）

广度优先遍历是另外一种遍历方法

package com.hugh.datastructure.binarytree.utils;

/**
 * @program: draft
 * @description: 二叉树节点
 * @author: Fly.Hugh
 * @create: 2020-08-12 04:58
 **/
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

package com.hugh.datastructure.binarytree.utils;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: draft
 * @description: 工具类
 * @author: Fly.Hugh
 * @create: 2020-08-12 06:10
 **/
public class TreeUtils {
    public static void main(String[] args) {
        TreeNode treeNode = generateTreeFromArray(3,9,20,null,null,15,7);
        System.out.println(treeNode.val);
        preOrderTraverse(treeNode);
    }

    /**
    * @author Fly.Hugh
    * @Description 从LeeCode给出的数组还原出树
    * @Date 6:28 2020/8/12
    * @Param [nums]
    * @return com.hugh.datastructure.binarytree.utils.TreeNode
    **/
    public static TreeNode generateTreeFromArray(Integer... nums) {
        if (nums.length == 0) {
            return null;
        }
        TreeNode head = new TreeNode(nums[0]);
        // stack的本质是由linked list或者array实现的
        LinkedList<TreeNode> subTree = new LinkedList<>();
        subTree.push(head);
        for (int i = 1; i < nums.length; i++) {
            if (!subTree.isEmpty()) {
                TreeNode cur = subTree.pop();
                if (nums[i] != null) {
                    cur.left = new TreeNode(nums[i]);
                    subTree.add(cur.left);
                }
                i++;
                if (i >= nums.length) {
                    break;
                }
                if (nums[i] != null) {
                    cur.right = new TreeNode(nums[i]);
                    subTree.add(cur.right);
                }

            } else {
                break;
            }
        }
        return head;
    }

    /**
    * @author Fly.Hugh
    * @Description 前序遍历
    * @Date 6:26 2020/8/12
    * @Param [root]
    * @return void
    **/
    public static void preOrderTraverse(TreeNode root) {
        if (root != null) {
            System.out.print(root.val+"  ");
            preOrderTraverse(root.left);
            preOrderTraverse(root.right);
        }
    }

    /**
    * @author Fly.Hugh
    * @Description 中序遍历
    * @Date 6:27 2020/8/12
    * @Param [root]
    * @return void
    **/
    public void inOrderTraverse(TreeNode root) {
        if (root != null) {
            inOrderTraverse(root.left);
            System.out.print(root.val+"  ");
            inOrderTraverse(root.right);
        }
    }

    /**
    * @author Fly.Hugh
    * @Description 后序遍历
    * @Date 6:27 2020/8/12
    * @Param [root]
    * @return void
    **/
    public void postOrderTraverse(TreeNode root) {
        if (root != null) {
            postOrderTraverse(root.left);
            postOrderTraverse(root.right);
            System.out.print(root.val+"  ");
        }
    }

    /**
    * @author Fly.Hugh
    * @Description 层次遍历
    * @Date 6:27 2020/8/12
    * @Param [root]
    * @return void
    **/
    public void levelTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val+"  ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /**
    * @author Fly.Hugh
    * @Description 深度优先遍历
    * @Date 6:28 2020/8/12
    * @Param [root]
    * @return void
    **/
    public void depthOrderTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val+"  ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    /**
    * @author Fly.Hugh
    * @Description 广度优先遍历
    * @Date 6:36 2020/8/12
    * @Param [nodeHead]
    * @return void
    **/
    public void BroadFirstSearch(TreeNode nodeHead) {
        if(nodeHead==null) {
            return;
        }
        Queue<TreeNode> myQueue=new LinkedList<>();
        myQueue.add(nodeHead);
        while(!myQueue.isEmpty()) {
            TreeNode node=myQueue.poll();
            System.out.print(node.val+" ");
            if(null!=node.left) {
                myQueue.add(node.left);    //深度优先遍历，我们在这里采用每一行从左到右遍历
            }
            if(null!=node.right) {
                myQueue.add(node.right);
            }

        }
    }
}

树题通用模板

void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

套用模板：求二叉树中最大路径和

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;
import com.hugh.datastructure.binarytree.utils.TreeUtils;

/**
 * @Author Fly.Hugh
 * @Date 2020/8/12 15:01
 * @Version 1.0
 **/
public class BinaryTreeMaximumPathSum {
    public static void main(String[] args) {
        TreeNode root = TreeUtils.generateTreeFromArray(-10,9,20,null,null,15,7);
        BinaryTreeMaximumPathSum binaryTreeMaximumPathSum = new BinaryTreeMaximumPathSum();
        int i = binaryTreeMaximumPathSum.maxPathSum(root);
        System.out.println(i);
    }

    /**
     * 求二叉树中的最大路径和
     * 原题描述：
     * 给定一个非空二叉树，返回其最大路径和。
     * 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
     * 示例 1:
     *
     * 输入: [1,2,3]
     *
     *        1
     *       / \
     *      2   3
     *
     * 输出: 6
     *
     * 示例 2:
     *
     * 输入: [-10,9,20,null,null,15,7]
     *
     *    -10
     *    / \
     *   9  20
     *     /  \
     *    15   7
     *
     * 输出: 42
     *
     * -------------------------------------------------------
     *
     * 题意：从树中任意一个节点出发，寻找最大的路径和，就是在该节点的 子树 中寻找以该节点所在的一条路径，使得该路径上的节点值之和最大。
     * 从下而上进行分析求解。
     * 官方题解中有个贡献值的概念：
     *
     * 1、空节点的最大贡献值等于 0。
     * 2、非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）,考虑到如果叶节点都为负值时，只是单纯引入最大贡献值的子节点也是不太恰当的，所以如果两个子节点都为负值时，此节点的最大贡献值为它本身的值。
     *
     * 这里的贡献值呢，就是如果把该节点作为路径的一个节点，它所能提供的最大路径选择。即到当前节点后，选择下一步的节点的时候选择两个子节点中贡献值大的那个节点，来保证路径最大。
     *
     * 下面进行分析：就用官方题解这个二叉树来举例说明。
     *
     * ------------------------------------------------------
     * 我的理解
     * 路径，可以理解为指向，根据LeeCode的用例，每个节点都是往下一层指向两个节点，如果想把这个路径传递得尽可能长，只有可能根据箭头的方向，左右各找到一个点。
     *
     * 从思路上面来讲这题肯定是要遍历的。
     *
     * @param root
     * @return
     */
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    int maxSum = Integer.MIN_VALUE;

    /**
     * 本质上是后序遍历。
     *
     * 要讨论四种情况 四种情况分别是
     *
     * 单个数字最大值，
     * left + cur最大，
     * cur + right最大，
     * left + right + cur最大，
     * 四种
     *
     * 一，二，三这几种情况都可以作为树的一个子树再计算，但第四种是不能作为一个子树再计算的
     * @param node
     * @return
     */
    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }
    /**
     * 这题得递归手法是之前见过的，通过引入第三个变量来完成递归的输出。
     * 在这个递归的过程中，原函数仅仅用来返回结果，递归另外起了一个函数，然后在这个另外起的函数里面进行递归
     * 返回的值回到上面的left/right Gain里面继续参加下面的计算。
     **/
}

树的高度

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;
import com.hugh.datastructure.binarytree.utils.TreeUtils;

/**
 * @program: draft
 * @description: 树的高度
 * @author: Fly.Hugh
 * @create: 2020-08-12 06:56
 **/
public class MaximumDepthOfBinaryTree {
    public static void main(String[] args) {
        TreeNode node = TreeUtils.generateTreeFromArray(3, 9, 20, null, null, 15, 7);
        int i = new MaximumDepthOfBinaryTree().maxDepth(node);
        System.out.println(i);
    }

    /**
    * @author Fly.Hugh
    * @Description 又是一种全新的递归形式
     * 再接触几种递归应该就能总结出属于我自己的递归之道。
     * 每次有一层都会加一。
     *
     * 求二叉树的最大深度，根的深度是0，其实就是在求离根节点距离最远的叶节点的和根节点的距离。
    * @Date 7:04 2020/8/12
    * @Param [root]
    * @return int
    **/
    public int maxDepth(TreeNode root) {
        return (root == null) ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

判断是否是平衡二叉树

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;
import com.hugh.datastructure.binarytree.utils.TreeUtils;

/**
 * @Author Fly.Hugh
 * @Date 2020/8/13 10:42
 * @Version 1.0
 **/
public class BalancedBinaryTree {
    public static void main(String[] args) {
        TreeNode root = TreeUtils.generateTreeFromArray(1, 2, 2, 3, null, null, 3, 4, null, null, 4);
        TreeUtils.preOrderTraverse(root);

        BalancedBinaryTree balancedBinaryTree = new BalancedBinaryTree();
        boolean balanced = balancedBinaryTree.isBalanced(root);
        System.out.println(balanced);

    }

    /**
     * 判断是否是平衡二叉树（每个节点的子数深度不超过1）
     * 借助外面的变量实现递归，加上了一个尾部遍历，第三次接触这种递归方式
     */
    private boolean flag = true;

    public boolean isBalanced(TreeNode root) {
        getMaxDepth(root);
        return flag;
    }

    public int getMaxDepth(TreeNode node){
        if(node == null) return 0;
        int left = getMaxDepth(node.left);
        int right = getMaxDepth(node.right);
        if(Math.abs(left - right) > 1) flag = false;
        return 1 + Math.max(left, right);
    }
}

求二叉树的直径

基本套路和求二叉树的最大路径和相同

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

/**
 * @Author Fly.Hugh
 * @Date 2020/8/13 11:33
 * @Version 1.0
 **/
public class DiameterOfBinaryTree {
    public static void main(String[] args) {

    }

    /**
     * 求二叉树的直径
     */
    private int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        getDiameter(root);
        return diameter;
    }

    public int getDiameter(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = getDiameter(node.left);
        int right = getDiameter(node.right);
        diameter = Math.max(diameter, (left + right));
        return 1 + Math.max(left, right);
    }
}

翻转树

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;
import com.hugh.datastructure.binarytree.utils.TreeUtils;

/**
 * @Author Fly.Hugh
 * @Date 2020/8/13 14:17
 * @Version 1.0
 **/
public class InvertBinaryTree {
    public static void main(String[] args) {
        TreeNode root = TreeUtils.generateTreeFromArray(1, 2, 3, 4, 5, 6, 7);

        InvertBinaryTree InvertBinaryTree = new InvertBinaryTree();
        TreeNode treeNode = InvertBinaryTree.invertTree(root);
        TreeUtils.preOrderTraverse(treeNode);
    }

    /**
     * 翻转树
     * Max Howell 被Google难住的题目
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    public TreeNode inverTree_improve(TreeNode root) {
        if (root == null) return root;
        TreeNode left = root.left;
        root.left = inverTree_improve(root.right);
        root.right = inverTree_improve(left);
        return root;
    }
}

合并二叉树

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;
import com.hugh.datastructure.binarytree.utils.TreeUtils;

/**
 * @program: draft
 * @description: 归并两棵树
 * @author: Fly.Hugh
 * @create: 2020-08-14 00:44
 **/
public class MergeTwoBinaryTrees {
    public static void main(String[] args) {
        TreeNode t1 = TreeUtils.generateTreeFromArray(1, 3, 2, 5);
        TreeNode t2 = TreeUtils.generateTreeFromArray(2, 1, 3, null, 4, null, 7);
        TreeNode root = new MergeTwoBinaryTrees().mergeTrees(t1, t2);
        TreeUtils.preOrderTraverse(root);
    }

    /**
    * @author Fly.Hugh
    * @Description 这题，总的来说还是在公式里面，有个特点就是输入是两个，输出却只有一个
     * 这种多输入 单输出的递归，值得注意一下
     * 可以新建一个TreeNode或者直接在原先的某一个树上直接修改。
     * 原理也很简单，直接从t1最左边的节点，继续往下（不够从t2左边拉），到了最下面之后然后回到上一层，再讨论右边，就这样逐层递归。
    * @Date 0:46 2020/8/14
    * @Param [t1, t2]
    * @return com.hugh.datastructure.binarytree.utils.TreeNode
    **/
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return null;
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right); // 这边的left 和 right还容易写错。。。。
        return t1;
    }
}

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

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

import java.util.ArrayList;

/**
 * @Author Fly.Hugh
 * @Date 2020/8/14 9:13
 * @Version 1.0
 **/
public class PathSum {
    public static void main(String[] args) {

    }

    /**
     * 给定一个int Sum，要判断是否存在一条路径，从Root到Leaf，各个节点的和加起来等于Sum.
     *
     * 一种新的类型的递归，返回值是bool，通过 || 的特性，不断向上返回bool.有一个为true就一直为true.
     * @param root
     * @param sum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.left == null && root.right == null && root.val == sum) return true;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

PathSumIII

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

/**
 * @program: draft
 * @description: 统计路径和等于一个数的路径数量
 * @author: Fly.Hugh
 * @create: 2020-08-15 01:39
 **/
public class PathSumIII {
    public static void main(String[] args) {

    }

    /**
    * @author Fly.Hugh
    * @Description
     * 给定一个二叉树，它的每个结点都存放着一个整数值。
     * 找出路径和等于给定数值的路径总数。
     * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
     * 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
     *
     * 示例：
     * root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
     *
     *       10
     *      /  \
     *     5   -3
     *    / \    \
     *   3   2   11
     *  / \   \
     * 3  -2   1
     *
     * 返回 3。和等于 8 的路径有:
     *
     * 1.  5 -> 3
     * 2.  5 -> 2 -> 1
     * 3.  -3 -> 11
     *
     * 这道题目要和前面一题结合起来看，（PathSum）
     *
    * @Date 1:41 2020/8/15
    * @Param [root, sum]
    * @return int
    **/
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        int ret = 0;
        // 这里的用法十分巧妙，并没有全部递归下去，如果全部递归下去的则没有意义，递归，不要纠结在头脑风暴上
        // 这里左右节点都是用的是无限递归，但是头节点仅仅递归了一次，总的来说还是在套用那个模板，这里的头节点，仅仅是计算整个树的头节点符合要求的个数。
        ret = pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
        return ret;
    }

    private int pathSumStartWithRoot(TreeNode root, int sum) {
        if (root == null) return 0;
        int ret = 0;
        // 这里的判断条件十分重要，联想到之前的一直查找到跟节点的那个条件，那里是 left == null && right == null && sum = root.val ，和这里的区别就是不一定要到根节点，这里只要满足连续的条件即可
        if (sum == root.val) ret++;
        ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val);
        return  ret;
    }
    /**
    * @author Fly.Hugh
    * @Description 整道题目使用了两次递归，第一次递归，套用模板，深度遍历，第二个递归，其实仍然在求和的模板之内。
    * @Date 2:41 2020/8/15
    **/
}

SubtreeOfAnotherTree

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

/**
 * @program: draft
 * @description: 子树
 * @author: Fly.Hugh
 * @create: 2020-08-15 02:48
 **/
public class SubtreeOfAnotherTree {
    public static void main(String[] args) {

    }

    /**
    * @author Fly.Hugh
    * @Description
     *
     * 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
     *
     * 示例 1:
     * 给定的树 s:
     *
     *      3
     *     / \
     *    4   5
     *   / \
     *  1   2
     * 给定的树 t：
     *
     *    4
     *   / \
     *  1   2
     * 返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
     *
     * 示例 2:
     * 给定的树 s：
     *
     *      3
     *     / \
     *    4   5
     *   / \
     *  1   2
     *     /
     *    0
     * 给定的树 t：
     *
     *    4
     *   / \
     *  1   2
     * 返回 false。
     *
     * 看到题目描述，首先判断一个树是否是另一棵树的子树，很明显想到可以用递归，但是两棵树完全相同也可以看做一棵树是另一棵树的子树。
     * 所以自然而然想到用一个判断两棵树是否相同的递归函数。
     *
     * 第一个递归和 PathSumIII 第一个递归的思想相同
     * 第二个递归则完完全全是 单独的问题，两树是否相同。 也就是LeeCode 100.题
     *
     *
    * @Date 2:49 2020/8/15
    * @Param [s, t]
    * @return boolean
    **/
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;

        return isSameTree(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }

    /**
    * @author Fly.Hugh
    * @Description 这边 isSameTree的判断可以简化，要注意为什么可以这么写。
     *     if (t == null && s == null) return true;
     *     if (t == null || s == null) return false;
     *     if (t.val != s.val) return false;
     *     return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
     *
     *     可以写成这样，要考虑到满足上一个条件之后就已经直接return出去了，不会参与下面的村循环，这种情况下其实和if else的语法是一样的。
    * @Date 3:41 2020/8/15
    **/
}

SymmetricTree

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: draft
 * @description: 对称树
 * @author: Fly.Hugh
 * @create: 2020-08-15 03:47
 **/
public class SymmetricTree {
    public static void main(String[] args) {

    }

    /**
    * @author Fly.Hugh
    * @Description
     * 给定一个二叉树，检查它是否是镜像对称的。
     *
     *
     * 例如，二叉树[1,2,2,3,4,4,3] 是对称的。
     *
     *     1
     *    / \
     *   2   2
     *  / \ / \
     * 3  4 4  3
     *
     *
     * 但是下面这个[1,2,2,null,3,null,3] 则不是镜像对称的:
     *
     *     1
     *    / \
     *   2   2
     *    \   \
     *    3    3
     *
     * 进阶：
     *
     * 你可以运用递归和迭代两种方法解决这个问题吗？
     *
     * 先说递归，其实这题又转换成了LeeCode 100题的变种。100题是两棵树是否相等，这题是两颗树是否对称。
     *
    * @Date 3:48 2020/8/15
    * @Param [root]
    * @return boolean
    **/
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetric(root.left, root.right);
    }

    private boolean isSymmetric(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val != q.val) return false;
        return isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);
    }

    //==================================================迭代>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    public boolean isSymmetricIter(TreeNode root) {
        return check(root, root);
    }

    /**
    * @author Fly.Hugh
    * @Description
     * 我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。
     * 初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），
     * 然后将两个结点的左右子结点按相反的顺序插入队列中。
     * 当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
    * @Date 4:13 2020/8/15
    * @Param [u, v]
    * @return boolean
    **/
    public boolean check(TreeNode u, TreeNode v) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(u);
        q.offer(v);
        while (!q.isEmpty()) {
            u = q.poll();
            v = q.poll();
            if (u == null && v == null) {
                continue;
            }
            if ((u == null || v == null) || (u.val != v.val)) {
                return false;
            }

            q.offer(u.left);
            q.offer(v.right);

            q.offer(u.right);
            q.offer(v.left);
        }
        return true;
    }
}

SumOfLeftLeaves

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

import static com.hugh.datastructure.binarytree.utils.TreeUtils.generateTreeFromArray;

/**
 * @program: draft
 * @description: 左叶子之和
 * @author: Fly.Hugh
 * @create: 2020-08-15 04:17
 **/
public class SumOfLeftLeaves {
    public static void main(String[] args) {
        TreeNode root = generateTreeFromArray(3,9,20,null,null,15,7);
        int i = new SumOfLeftLeaves().sumOfLeftLeavesNiubi(root);
        System.out.println(i);
    }


    /**
    * @author Fly.Hugh
    * @Description
     * 计算给定二叉树的所有左叶子之和。
     *
     * 示例：
     *
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     *
     * 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
     *
     * 递归解法一：
     * 深度优先遍历，很简单，问题的关键就在于什么是左节点。
     *
    * @Date 5:05 2020/8/15
    * @Param [root]
    * @return int
    **/
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if(root.left != null && root.left.left == null && root.left.right == null) {
            sum += root.left.val;
        }

        sumOfLeftLeaves(root.left);
        sumOfLeftLeaves(root.right);
        return sum;
    }

    private int sum;

    //==================================================更牛逼的迭代>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

    /**
    * @author Fly.Hugh
    * @Description
     * 完全从语义出发，虽然写起来更麻烦一点，用了两个判断，但是让人一看就懂，牛逼。
    * @Date 5:15 2020/8/15
    * @Param [root]
    * @return int
    **/
    public int sumOfLeftLeavesNiubi(TreeNode root) {
        if (root == null) return 0;
        if (isLeaf(root.left)) return root.left.val + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }

    private boolean isLeaf(TreeNode root) {
        if (root == null) {
            return false;
        }

        return root.left == null && root.right == null;
    }

}

LongestUnivaluePath

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

/**
 * @program: draft
 * @description: 最长同值路径
 * @author: Fly.Hugh
 * @create: 2020-08-15 05:28
 **/
public class LongestUnivaluePath {
    public static void main(String[] args) {

    }

    /**
    * @author Fly.Hugh
    * @Description
     * 给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
     *
     * 注意：两个节点之间的路径长度由它们之间的边数表示。
     *
     * 示例 1:
     *
     * 输入:
     *
     *               5
     *              / \
     *             4   5
     *            / \   \
     *           1   1   5
     * 输出:
     *
     * 2
     * 示例 2:
     *
     * 输入:
     *
     *               1
     *              / \
     *             4   5
     *            / \   \
     *           4   4   5
     * 输出:
     *
     * 2
     * 注意: 给定的二叉树不超过10000个结点。树的高度不超过1000。
     *
    * @Date 5:28 2020/8/15
    * @Param [root]
    * @return int
    **/
    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return path;
    }

    private int path = 0;

    private int dfs(TreeNode root){
        if (root == null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        int leftPath = root.left != null && root.left.val == root.val ? left + 1: 0;
        int rightPath = root.right != null && root.right.val == root.val ? right + 1: 0;
        path = Math.max(path, rightPath+leftPath);
        return Math.max(leftPath, rightPath);
    }
    /**
    * @author Fly.Hugh
    * @Description
     * 这道题目值得好好思考一下
     * 二叉树递归的难点就在于怎么构思：子节点向父节点返回的是什么?或者说，当前节点向其父节点返回的是什么?
     * 这题中，当前节点返回给父节点的值就是：
     *
     * 从当前节点出发，向下延伸与其值相同的最大深度
     *
     * 于是返回值分两种情况：
     * 1.                                    if( 如果当前节点与其左右节点都不相等)，那么深度为0，则返回0
     * 2. else，                             这个最大深度就取其 左右子树返回值中的较大者 + 1
     *
     * 然后，在上面这个dfs的遍历过程中，还可以做一些其他的事情，这题做的就是 计算路径长度。由于子树的返回值已经确定了，所以需要额外的一个全局变量。
    * @Date 8:14 2020/8/15
    **/
}

HouseRobberIII

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

/**
 * @program: draft
 * @description: 间隔遍历
 * @author: Fly.Hugh
 * @create: 2020-08-15 16:23
 **/
public class HouseRobberIII {
    public static void main(String[] args) {

    }

    /**
    * @author Fly.Hugh
    * @Description
     * 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
     *
     * 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
     *
     * 示例 1:
     *
     * 输入: [3,2,3,null,3,null,1]
     *
     *      3
     *     / \
     *    2   3
     *     \   \
     *      3   1
     *
     * 输出: 7
     * 解释:小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
     * 示例 2:
     *
     * 输入: [3,4,5,1,3,null,1]
     *
     *      3
     *     / \
     *    4   5
     *   / \   \
     *  1   3   1
     *
     * 输出: 9
     * 解释:小偷一晚能够盗取的最高金额= 4 + 5 = 9.
     *
     * 这题我第一时间想复杂了，要注意题目，必须是从根节点开始取得。
     * 那么两情况分别是取根节点（就是本节点和间隔一层的两个节点*（前提条件是判断存不存在子节点））和不取根节点的情况（就是两个子节点）
     *
    * @Date 16:24 2020/8/15
    * @Param [root]
    * @return int
    **/
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int singleSum = root.val;
        if (root.left != null) singleSum += rob(root.left.left) + rob(root.left.right);
        if (root.right!= null) singleSum += rob(root.right.left) + rob(root.right.right);
        int doubleSum = rob(root.left) + rob(root.right);
        return Math.max(doubleSum, singleSum);
    }
}

SecondMinimumNodeInABinaryTree

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

/**
 * @program: draft
 * @description: 找出二叉树中第二小的节点
 * @author: Fly.Hugh
 * @create: 2020-08-15 18:11
 **/
public class SecondMinimumNodeInABinaryTree {
    public static void main(String[] args) {

    }

    /**
    * @author Fly.Hugh
    * @Description
     * 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
     *
     * 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
     *
     * 示例 1:
     *
     * 输入:
     *     2
     *    / \
     *   2   5
     *      / \
     *     5   7
     *
     * 输出: 5
     * 说明: 最小的值是 2 ，第二小的值是 5 。
     * 示例 2:
     *
     * 输入:
     *     2
     *    / \
     *   2   2
     *
     * 输出: -1
     * 说明: 最小的值是 2, 但是不存在第二小的值。
     *
    * @Date 18:12 2020/8/15
    * @Param [root]
    * @return int
    **/
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) return -1;
        if (root.left == null && root.right == null) return -1;
        int leftValue = root.left.val;
        int rightValue = root.right.val;
        // 巧妙，太牛了，几个点，首先这种写法从上到下都简化了if else的else，其次这里的判断条件结合题意：每个子树的头节点总是后面最小的值，这里的值不是root，没必要再找了，就是这个最小了。在后面return.
        if (leftValue == root.val) leftValue = findSecondMinimumValue(root.left);
        if (rightValue == root.val) rightValue = findSecondMinimumValue(root.right);
        if (leftValue != -1 && rightValue != -1) return Math.min(leftValue, rightValue);
        if (leftValue == -1) return rightValue;
        return leftValue;
    }
}

一棵树每层节点的平均数

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;
import com.hugh.datastructure.binarytree.utils.TreeUtils;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author Fly.Hugh
 * @Date 2020/8/20 10:07
 * @Version 1.0
 **/
public class AverageOfLevelsInBinaryTree {
    public static void main(String[] args) {
        TreeNode root = TreeUtils.generateTreeFromArray(1, 2, 3, 4, 5, 6, 7);
        
    }

    /**
     * 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
     *
     * 示例 1：
     *
     * 输入：
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 输出：[3, 14.5, 11]
     * 解释：
     * 第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
     *
     * 提示：
     *
     * 节点值的范围在32位有符号整数范围内。
     *
     * @param root
     * @return
     */
    public List<Double> averageOfLevels(TreeNode root) {
        ArrayList<Double> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> myQueue = new LinkedList<>();
        myQueue.add(root);
        while (!myQueue.isEmpty()) {
            int cnt = myQueue.size();
            double sum = 0;
            for (int i = 0; i < cnt; i++) {
                TreeNode poll = myQueue.poll();
                sum += poll.val;
                if (poll.left != null) {
                    myQueue.add(poll.left);
                }
                if (poll.right != null) {
                    myQueue.add(poll.right);
                }
            }
            ret.add(sum / cnt);
        }

        return ret;
    }

    public static void broadFirstSearch(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> myQueue = new LinkedList<>();
        myQueue.add(root);
        while (!myQueue.isEmpty()) {
            TreeNode poll = myQueue.poll();
            System.out.print(poll.val + " ");
            if (poll.left != null) {
                myQueue.add(poll.left);
            }
            if (poll.right != null) {
                myQueue.add(poll.right);
            }
        }
    }
}

得到左下角的节点

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author Fly.Hugh
 * @Date 2020/8/20 12:14
 * @Version 1.0
 **/
public class FindBottomLeftTreeValue {
    public static void main(String[] args) {

    }

    /**
     * 给定一个二叉树，在树的最后一行找到最左边的值。
     *
     * 示例 1:
     *
     * 输入:
     *
     *     2
     *    / \
     *   1   3
     *
     * 输出:
     * 1
     *
     * 示例 2:
     *
     * 输入:
     *
     *         1
     *        / \
     *       2   3
     *      /   / \
     *     4   5   6
     *        /
     *       7
     *
     * 输出:
     * 7
     *
     * 注意: 您可以假设树（即给定的根节点）不为 NULL。
     * @param root
     * @return
     */
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> myQueue = new LinkedList<>();
        myQueue.add(root);
        while (!myQueue.isEmpty()) {
            root = myQueue.poll();

            // 顺序很重要 如果是left防癌前
            if (root.right != null) {
                myQueue.add(root.right);
            }

            if (root.left != null) {
                myQueue.add(root.left);
            }
        }
        return root.val;
    }
}

非递归遍历二叉树

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

import java.util.*;

/**
 * @program: draft
 * @description: 非递归实现前中后序遍历
 * @author: Fly.Hugh
 * @create: 2020-08-21 05:45
 **/
public class BinaryTreeOrderTraversal {
    public static void main(String[] args) {

    }

    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop == null) continue;
            ret.add(pop.val);
            stack.push(pop.right);
            stack.push(pop.left);
        }
        return ret;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            ret.add(node.val);
            cur = node.right;
        }
        return ret;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop == null) continue;
            ret.add(pop.val);
            stack.push(pop.left);
            stack.push(pop.right);
        }
        Collections.reverse(ret);
        return ret;
    }
}

BST

二叉查找树(BST)

根节点大于等于左子树的所有节点，小于等于右子树的所有节点。

二叉查找树使用中序遍历是有序的。

修剪二叉查找树

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

/**
 * @Author Fly.Hugh
 * @Date 2020/8/21 12:40 下午
 * @Version 1.0
 **/
public class TrimBST {
    public static void main(String[] args) {

    }

    /**
     * 给定一个二叉搜索树，同时给定最小边界L和最大边界R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
     *
     * 示例 1:
     *
     * 输入:
     *     1
     *    / \
     *   0   2
     *
     *   L = 1
     *   R = 2
     *
     * 输出:
     *     1
     *       \
     *        2
     * 示例 2:
     *
     * 输入:
     *     3
     *    / \
     *   0   4
     *    \
     *     2
     *    /
     *   1
     *
     *   L = 1
     *   R = 3
     *
     * 输出:
     *       3
     *      /
     *    2
     *   /
     *  1
     *
     * @param root
     * @param L
     * @param R
     * @return
     */
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return null;
        if (root.val > R) return trimBST(root.left, L, R);
        if (root.val < L) return trimBST(root.right, L, R);
        root.left = trimBST(root.left,L,R);
        root.right = trimBST(root.right,L,R);
        return root;
    }
}

寻找二叉查找树的第 k 个元素

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

/**
 * @Author Fly.Hugh
 * @Date 2020/8/21 3:12 下午
 * @Version 1.0
 **/
public class KthSmallestElementInABST {
    public static void main(String[] args) {

    }

    /**
     * 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
     * <p>
     * 说明：
     * 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
     * <p>
     * 示例 1:
     * <p>
     * 输入: root = [3,1,4,null,2], k = 1
     * 3
     * / \
     * 1   4
     * \
     * 2
     * 输出: 1
     * 示例 2:
     * <p>
     * 输入: root = [5,3,6,2,4,null,null,1], k = 3
     * 5
     * / \
     * 3   6
     * / \
     * 2   4
     * /
     * 1
     * 输出: 3
     * 进阶：
     * 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
     *
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest(TreeNode root, int k) {
        inOrder(root, k);
        return back;
    }

    private int count = 0;
    private int back;

    private void inOrder(TreeNode root, int k) {
        if (root == null) return;
        inOrder(root.left, k);
        count++;
        if (count == k) {
            back = root.val;
            return;
        }
        inOrder(root.right, k);
    }

    //==================================================分割符>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

    /**
     * 说实话 上面的解法，我刚开始看LeeCOde的时候还感觉挺有意思，到了现在已经没有任何惊喜了
     * 简单的中序遍历
     * 下面的这个解法别有新意。
     * 从Count入手。
     *
     * @param root
     * @param k
     * @return
     */
    public int kthSmallestNiu(TreeNode root, int k) {
        int leftCnt = count(root.left);
        if (leftCnt == k-1) return root.val;
        if (leftCnt > k-1) return kthSmallestNiu(root.left, k);
        return kthSmallestNiu(root.right, k - leftCnt - 1);
    }

    private int count(TreeNode root) {
        if (root == null) return 0;
        return 1 + count(root.left) + count(root.right);
    }

}

把二叉查找树每个节点的值都加上比它大的节点的值

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;
import com.hugh.datastructure.binarytree.utils.TreeUtils;

/**
 * @Author Fly.Hugh
 * @Date 2020/8/28 3:00 下午
 * @Version 1.0
 **/
public class ConvertBSTToGreaterTree {
    public static void main(String[] args) {
        TreeNode treeNode = TreeUtils.generateTreeFromArray(5, 2, 13);
        ConvertBSTToGreaterTree ct = new ConvertBSTToGreaterTree();
        TreeNode root = ct.convertBST(treeNode);
    }

    /**
     * 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，
     * 使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
     *
     *
     *
     * 例如：
     *
     * 输入: 原始二叉搜索树:
     *               5
     *             /   \
     *            2     13
     *
     * 输出: 转换为累加树:
     *              18
     *             /   \
     *           20     13
     *
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {
        traver(root);
        return root;
    }

    private int sum = 0;

    /**
     * BST的中序遍历就是从小到大,
     * 那么反过来就是从大到小,然后累加就好了.
     * @param root
     */
    private void traver(TreeNode root) {
        if(root == null) return;
        traver(root.right);
        sum += root.val;
        root.val = sum;
        traver(root.left);
    }
}

二叉搜索树最近公共先祖

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

/**
 * @Author Fly.Hugh
 * @Date 2020/8/28 6:24 下午
 * @Version 1.0
 **/
public class LowestCommonAncestor {
    public static void main(String[] args) {

    }

    /**
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     *
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，
     * 最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     *
     * 例如，给定如下二叉搜索树: root =[6,2,8,0,4,7,9,null,null,3,5]
     *
     * 示例 1:
     *
     * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
     * 输出: 6
     * 解释: 节点 2 和节点 8 的最近公共祖先是 6。
     * 示例 2:
     *
     * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
     * 输出: 2
     * 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 整体解决模式其实和之前那个范围 p 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;
    }
}

二叉树最近公共先祖

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

/**
 * @program: draft
 * @description: 二叉树的最近公共祖先
 * @author: Fly.Hugh
 * @create: 2020-08-29 06:56
 **/
public class LowestCommonAncestorⅡ {
    public static void main(String[] args) {

    }

    /**
    * @author Fly.Hugh
    * @Description
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     *
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     *
     * 例如，给定如下二叉树: root =[3,5,1,6,2,0,8,null,null,7,4]
     *
     * 示例 1:
     *
     * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
     * 输出: 3
     * 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
     * 示例2:
     *
     * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
     * 输出: 5
     * 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
     * 
     *
     * 说明:
     *
     * 所有节点的值都是唯一的。
     * p、q 为不同节点且均存在于给定的二叉树中。
     *
    * @Date 6:57 2020/8/29
    * @Param [root, p, q]
    * @return com.hugh.datastructure.binarytree.utils.TreeNode
    **/
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        /**
        * @author Fly.Hugh
        * @Description
         * 首先想到的是链表相交，求第一个交点的算法思想。
         *
         * 如果每个节点有指向父节点的指针的话，我们就可以把给的两个节点当做链表头，树的根是链表尾部。
         * 这样问题就转化为了求两个相交链表的第一个交点。
         *
         * 但是题目给的是一个普通的二叉树，没有父节点指针，所以就需要想其他方法了。
         *
         * 然后是初级递归
         *
         * 先判断公共祖先是否在左子树，是则找到
         * 再判断公共祖先是否在右子树，是则找到
         * 当前根是不是公共祖先，是则找到
         * 当前树没有公共祖先
         *
         * 这里有一个关键问题：怎么判断当前根是不是公共祖先呢？
         * 这个貌似又是一个递归题，可以拆解为根是不是节点A的祖先和根是不是节点B的祖先。
         * 两个同时满足了，根就是这两个节点的公共祖先。
         *
         * 这样这道题我们就做出来了，但是复杂度貌似有点高。
         * 对于每个子树，都进行了判断根是不是祖先，这样就相当于双层循环，复杂度是O(n^2)。
         *
         * 高级递归
         *
         * 其实，在初级递归的时候，复杂度之所高，就是需要在每个子树里判断一个根是不是两个节点的祖先。
         *
         * 这个判断在每个子树里是独立的，但是实际上树与树之间是有关系的。
         * 比如当前树的左儿子是节点A的祖先，那当前树的根肯定也是节点A的祖先。
         *
         * 递归的时候，如果能服用这个信息，则可以将复杂度降低到O(n)。
         *
         * -----
         *
         * 最近公共祖先的定义： 设节点 rootroot 为节点 p, qp,q 的某公共祖先，若其左子节点 root.leftroot.left 和右子节点 root.rightroot.right 都不是 p,qp,q 的公共祖先，则称 rootroot 是 “最近的公共祖先” 。
         *
         * 根据以上定义，若 rootroot 是 p, qp,q 的 最近公共祖先 ，则只可能为以下情况之一：
         *
         * p 和 q 在 rootroot 的子树中，且分列 rootroot 的 异侧（即分别在左、右子树中）；
         * p = rootp=root ，且 qq 在 rootroot 的左或右子树中；
         * q = rootq=root ，且 pp 在 rootroot 的左或右子树中；
         *
        **/
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        return left == null ? right : right == null ? left : root;
        // 后序遍历二叉树，如果找到了p或者q或者null（已经遍历完了这条线路），那么就返回这个本身
        // 然后活到整体的逻辑，最后一个判断非常关键，如果左右都不为空的话返回root根节点 也就是最近公共祖先。
    }
}

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

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

/**
 * @program: draft
 * @description: 从有序数组中构建二叉查找树
 * @author: Fly.Hugh
 * @create: 2020-08-31 21:55
 **/
public class ConvertSortedArrayToBinarySearchTree {
    public static void main(String[] args) {

    }

    /**
    * @author Fly.Hugh
    * @Description 
     * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
     *
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
     *
     * 示例:
     *
     * 给定有序数组: [-10,-3,0,5,9],
     *
     * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
     *
     *       0
     *      / \
     *    -3   9
     *    /   /
     *  -10  5
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    * @Date 21:57 2020/8/31
    * @Param [nums]
    * @return com.hugh.datastructure.binarytree.utils.TreeNode
    **/
    public TreeNode sortedArrayToBST(int[] nums) {
        // 双指针控制角标
        return toBST(nums, 0, nums.length - 1);
    }

    private TreeNode toBST(int[] nums, int sIdx, int eIdex) {
        // 注意循环停止的条件
        if(sIdx > eIdex) return null;
        int mIdex = (sIdx + eIdex) / 2;
        TreeNode root = new TreeNode(nums[mIdex]);
        root.left = toBST(nums, sIdx, mIdex - 1);
        root.right = toBST(nums, mIdex + 1, eIdex);
        return root;
    }
}

有序链表转换二叉搜索树

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;
import com.hugh.datastructure.linkedlist.leecode.standardutils.ListNode;

/**
 * @program: draft
 * @description: 根据有序链表构造平衡的二叉查找树BST
 * @author: Fly.Hugh
 * @create: 2020-08-31 23:22
 **/
public class ConvertSortedListToBinarySearchTree {
    public static void main(String[] args) {

    }

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */

    /**
     * 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;
     *     }
     * }
     */

    /**
    * @author Fly.Hugh
    * @Description
     * 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
     *
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
     *
     * 示例:
     *
     * 给定的有序链表： [-10, -3, 0, 5, 9],
     *
     * 一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
     *
     *       0
     *      / \
     *    -3   9
     *    /   /
     *  -10  5
     *
    * @Date 23:26 2020/8/31
    * @Param [head]
    * @return com.hugh.datastructure.binarytree.utils.TreeNode
    **/
    public TreeNode sortedListToBST(ListNode head) {
        //边界条件的判断
        if(head==null) return null;
        // 如果不加这个边界条件判断，在后面得断开链表环节会出现NullException
        if(head.next==null) return new TreeNode(head.val);
        //这里通过快慢指针找到链表的中间结点slow，pre就是中间
        //结点slow的前一个结点
        ListNode slow = head, fast = head, pre = null;
        //链表断开为两部分，一部分是node的左子节点，一部分是node
        //的右子节点
        while(fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        //node就是当前节点
        TreeNode node = new TreeNode(slow.val);
        //从head节点到pre节点是node左子树的节点
        node.left = sortedListToBST(head);
        //从slow.next到链表的末尾是node的右子树的结点 从这里也可以看到引入pre的原因，slow和pre分开了，这里才能引用slow.next
        node.right = sortedListToBST(slow.next);
        return node;
    }
}

在BST中寻找两节点差绝对值的最小值

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

/**
 * @Author Fly.Hugh
 * @Date 2020/9/1 12:06 下午
 * @Version 1.0
 **/
public class MinimumAbsoluteDifferenceInBST {
    public static void main(String[] args) {

    }

    /**
     * 给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
     *
     * 示例：
     *
     * 输入：
     *
     *    1
     *     \
     *      3
     *     /
     *    2
     *
     * 输出：
     * 1
     *
     * 解释：
     * 最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
     * 
     *
     * 提示：
     *
     * 树中至少有 2 个节点。
     * 本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
     *
     * @param root
     * @return
     */
    public int getMinimumDifference(TreeNode root) {
        find(root);
        return min;
    }

    private void find(TreeNode root) {
        if(root==null) return;
        find(root.left);
        if (pre != null) {
            // 中序遍历BST 严格递增
            min = Math.min(min,root.val - pre.val);
        }
        pre = root;
        find(root.right);
    }

    // BST的性质要利用起来 中序遍历，保存前一个节点
    int min = Integer.MAX_VALUE;
    TreeNode pre = null;
}

在二叉查找树中寻找两个节点，使它们的和为一个给定值

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

import java.util.HashSet;

/**
 * @Author Fly.Hugh
 * @Date 2020/9/1 11:43 上午
 * @Version 1.0
 **/
public class TwoSumIV {
    public static void main(String[] args) {

    }

    /**
     * 给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
     *
     * 案例 1:
     *
     * 输入: 
     *     5
     *    / \
     *   3   6
     *  / \   \
     * 2   4   7
     *
     * Target = 9
     *
     * 输出: True
     * 
     *
     * 案例 2:
     *
     * 输入: 
     *     5
     *    / \
     *   3   6
     *  / \   \
     * 2   4   7
     *
     * Target = 28
     *
     * 输出: False
     *
     * @param root
     * @param k
     * @return
     */
    public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> set = new HashSet<>();
        return find(root, k, set);
    }

    private boolean find(TreeNode root, int k, HashSet<Integer> set) {
        if(root==null) return false;
        if(set.contains(k - root.val)) return true;
        set.add(root.val);
        return find(root.left, k, set) || find(root.right, k, set);
    }
}

寻找二叉查找树中出现次数最多的值

package com.hugh.datastructure.binarytree.leecode;

import com.hugh.datastructure.binarytree.utils.TreeNode;

import java.util.ArrayList;

/**
 * @Author Fly.Hugh
 * @Date 2020/9/1 12:29 下午
 * @Version 1.0
 **/
public class FindModeInBinarySearchTree {
    public static void main(String[] args) {

    }

    /**
     * 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
     *
     * 假定 BST 有如下定义：
     *
     * 结点左子树中所含结点的值小于等于当前结点的值
     * 结点右子树中所含结点的值大于等于当前结点的值
     * 左子树和右子树都是二叉搜索树
     * 例如：
     * 给定 BST [1,null,2,2],
     *
     *    1
     *     \
     *      2
     *     /
     *    2
     * 返回[2].
     *
     * 提示：如果众数超过1个，不需考虑输出顺序
     *
     * 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
     *
     * @param root
     * @return
     */
    public int[] findMode(TreeNode root) {
        // 这个解法是为了最小的空间复杂度，仍然利用了BST的中序遍历递增的特性。
        final ArrayList<Integer> maxCntNums = new ArrayList<>();
        inOrder(root,maxCntNums);
        // ArrayList 转换 int[]
        int[] ret = new int[maxCntNums.size()];
        int idx = 0;
        for (int num :
                maxCntNums) {
            ret[idx++] = num;
        }
        return ret;
    }

    private void inOrder(TreeNode node, ArrayList<Integer> nums) {
        if (node == null) return;
        inOrder(node.left,nums);
        if (preNode != null) {
            if (preNode.val == node.val) curCnt++;
            else curCnt = 1;
        }
        if (curCnt > maxCnt) {
            maxCnt = curCnt;
            nums.clear();
            nums.add(node.val);
        } else if (curCnt == maxCnt) {
            nums.add(node.val);
        }
        preNode = node;
        inOrder(node.right,nums);
    }

    private int curCnt = 1;
    private int maxCnt = 1;
    private TreeNode preNode = null;
}

Trie树，字典树、单词查找树或键树哈希树的变种

典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

hash表，通过hash函数把所有的单词分别hash成key值，查询的时候直接通过hash函数即可，都知道hash表的效率是非常高的为O(1)，直接说字典树的查询效率比hash高，难道有比O(1)还快的- -。

hash：

当然对于单词查询，如果我们hash函数选取的好，计算量少，且冲突少，那单词查询速度肯定是非常快的。那如果hash函数的计算量相对大呢，且冲突律高呢？

这些都是要考虑的因素。且hash表不支持动态查询，什么叫动态查询，当我们要查询单词apple时，hash表必须等待用户把单词apple输入完毕才能hash查询。

当你输入到appl时肯定不可能hash吧。

字典树（tries树）：

对于单词查询这种，还是用字典树比较好，但也是有前提的，空间大小允许，字典树的空间相比较hash还是比较浪费的，毕竟hash可以用bit数组。

那么在空间要求不那么严格的情况下，字典树的效率不一定比hash若，它支持动态查询，比如apple，当用户输入到appl时，字典树此刻的查询位置可以就到达l这个位置，那么我在输入e时光查询e就可以了（更何况如果我们直接用字母的ASCII作下标肯定会更快）！字典树它并不用等待你完全输入完毕后才查询。

所以效率来讲我认为是相对的。

所以尽管哈希表可以在 O(1)O(1) 时间内寻找键值，却无法高效的完成以下操作：

找到具有同一前缀的全部键值。
按词典序枚举字符串的数据集。

本场景中，此Trie(读音try)是一个有根树，有以下特点：

最多 RR 个指向子结点的链接，其中每个链接对应字母表数据集中的一个字母。本文中假定 RR 为 26，小写拉丁字母的数量。
布尔字段，以指定节点是对应键的结尾还是只是键前缀。

package trie;

/**
 * @Author Fly.Hugh
 * @Date 2020/9/3 11:08
 * @Version 1.0
 **/
public class TrieNode {

    TrieNode[] child;

    boolean isEnd;

    public TrieNode() {
        this.child = new TrieNode[26];
        this.isEnd = false;
    }
}

package trie;

/**
 * @Author Fly.Hugh
 * @Date 2020/9/3 11:08
 * @Version 1.0
 **/
public class Trie {

    TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode p = root;
        for(int i = 0; i < word.length(); i ++) {
            char c = word.charAt(i);
            // 对应位置上只要不是空就代表有值，并不需要填入某个确定的char，[c - 'a'] 代表了index
            if(p.child[c - 'a'] == null) {
                p.child[c - 'a'] = new TrieNode();
            }
            // 有点类似与二叉树的node = node.next;
            p = p.child[c - 'a'];
        }
        p.isEnd = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode p = root;
        for(int i = 0; i < word.length(); i ++) {
            char c = word.charAt(i);
            if(p.child[c - 'a'] == null) {
                return false;
            }
            p = p.child[c - 'a'];
        }
        /*if(p.isEnd == true) {
            return true;
        }
        return false;*/
        return p.isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode p = root;
        for(int i = 0; i < prefix.length(); i ++) {
            char c = prefix.charAt(i);
            if(p.child[c - 'a'] == null) {
                return false;
            }
            p = p.child[c - 'a'];
        }
        return true;
    }
}

实现一个 Trie，用来求前缀和

package com.hugh.datastructure.binarytree.leecode;

/**
 * @program: draft
 * @description: 实现一个 Trie，用来求前缀和
 * @author: Fly.Hugh
 * @create: 2020-09-04 04:27
 **/
public class MapSum {
    /**
    * @author Fly.Hugh
    * @Description
     * 实现一个 MapSum 类里的两个方法，insert 和 sum。
     * 对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。
     * 对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。
     *
     * 示例 1:
     *
     * 输入: insert("apple", 3), 输出: Null
     * 输入: sum("ap"), 输出: 3
     * 输入: insert("app", 2), 输出: Null
     * 输入: sum("ap"), 输出: 5
     * 通过次数8,509提交次数14,004
     *
    * @Date 4:28 2020/9/4
    * @Param [args]
    * @return void
    **/
    public static void main(String[] args) {

    }

    private class Node {
        Node[] child = new Node[26];
        int value;
    }

    private Node root = new Node();

    /** Initialize your data structure here. */
    public MapSum() {

    }

    public void insert(String key, int val) {
        insert(key, root, val);
    }

    private void insert(String key, Node node, int val) {
        if (node == null) return;

        if (key.length() == 0) {
            node.value = val;
            return;
        }

        int index = indexForChar(key.charAt(0));

        if (node.child[index] == null) {
            node.child[index] = new Node();
        }
        insert(key.substring(1), node.child[index], val);
    }

    public int sum(String prefix) {
        return sum(prefix, root);
    }

    private int sum(String prefix, Node node) {
        if (node == null) return 0;
        if (prefix.length() != 0) {
            int index = indexForChar(prefix.charAt(0));
            return sum(prefix.substring(1), node.child[index]);
        }
        int sum = node.value;
        for (Node child : node.child) {
            sum += sum(prefix, child);
        }
        return sum;
    }

    private int indexForChar(char c) {
        return c - 'a';
    }
}