直接 Ctrl+f 搜索题目
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
- 直接遍历链表，对两个节点的值进行相加。注意两个链表长度可能不一，需要判断当前的链表节点存在。
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
-
翻转一次链表，遍历到 n 的位置删除节点后再翻转回来。注意需要对第一个节点做特殊处理，如果删除的是第一个节点，则直接返回
head.next就可以了。 -
先遍历一次链表计算出链表长度，再遍历一次链表，根据
curIndex + 1 === length - n的条件判断下一个节点是否是要删除的节点（curIndex从0开始）。同样需要对第一个节点做特殊处理。 -
先后指针。快指针先走 n-1 步后慢指针再开始从头节点开始走。当快指针走到最后一个结点的时候，慢指针就走到了倒数第n个结点。使用一个
pre = null来保存上一个节点，到达倒数第n个节点后使pre.next = slow.next再返回 head 即可。如果pre === null即要删除的是第一个节点，则直接返回slow.next。
证明：
- 假设总共有N个结点，则倒数第n个结点就是正数第 N-n+1 个结点。
- 从头结点正向走到第 N-n+1 个结点需要走 N-n 步，而从头节点到链表最后一个结点需要走 N-1 步，所以还剩 n+1 步。
- 即让快指针先走 n+1 步后再让慢指针同时走直到快指针走到链表尾即可。
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
-
建立一个新链表，遍历两个链表边比较节点值的大小边增加到新链表上。注意两个链表可能不等长，需要判断当前两个链表的节点是否存在。
-
递归：可以看成是由多个相同的合并操作组合成的，每个合并过程都包括比较并取节点的值作为新节点的值，继续比较剩下的两个链表并放回其结果作为当前新节点的 next 指向。
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
- 同上题，只要加一个 for 循环 k，两两合并最后成一个链表即可。但貌似更优解是使用优先队列。
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
- 递归：维护四个节点，取链表的第一个节点作为 first，第二个节点作为 second，第三个节点作为 three。只要使
second.next = first, 并递归操作 three，将其返回值赋值给first.next，每次递归都返回 second。
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
-
使用数组存储各个节点的值，再以此生成链表。注意为了避免 k 太大时循环太多次，使用
k = k % arr.length优化，每次移动相当于将数组的末元素放到首位置上，arr.unshift(arr.pop())。 -
相当于倒数第k个节点（正数第 len-k+1 个节点）变成了头节点，第 len-k 个节点变成了尾节点。所以移动到第len-k个节点，将其下一个节点缓存为新头节点，并将当前节点节点的 next 指向 null。再遍历到尾节点将其 next 修改为 head 即可。
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
-
使用两个变量 pre（初始化为null）和 end（初始化为 cur.next）记录重复节点的前一个节点和最后一个节点。循环链表，遇到有重复值的节点，就嵌套一次循环直至重复结束。如果
pre === null（首节点就重复了），则直接head = end.next，否则pre.next = end.next，以此截断调重复的节点。 -
递归。若当前节点和下一个节点值不重复，则递归其 next 指针并将返回值作为当前节点的 next。若值重复了，则循环直至不重复，将不重复的节点进行递归并返回其返回值（作为上一次递归节点的 next）。
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
-
循环链表，遇到重复的就把当前节点的 next 修改为 next.next。
-
递归。和上一题的区别在于，本题先递归求解当前节点的 next，这样就可以使得重复元素也出现一次。之后再判断当前节点和下一个节点是否值重复，重复的话则循环直至不重复再返回。
-
使用一个数组记录每个节点值出现的次数（边循环边记录），判断当前节点的下一个节点值对应的数组值是否大于1，是则将 next 修改为 next.next。
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
-
双指针，一个链表收集小于x的，一个链表收集大于等于x的，最后把后者连接到前者上。
-
先把结点值缓存到两个数组，然后根据小的数组链接链表，再继续连接大的数组。
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
- 将pre从m不断推移到n，把它连接到next后面并修改它的next指向，再将next连接到before后面。循环这个过程即可。例如 1->2->3->4->5->NULL,m=2,n=4。将pre(2)放到next(3)后面，就成了 3->2，改变pre(2)的next指向就成了3-2->4->5->NULL。再把next(3)链接到before(1)后面，1->3-2->4->5->NULL，以此类推。
- before为开始翻转的前一个结点
- pre为要开始翻转的结点
- next为pre的下一个结点
- 遍历链表，使用数组暂存 m-n 节点的值（将节点值插入到数组头部）。再遍历一边，根据数组修改 m-n 的节点值。可以使用同一个函数进行两次遍历，再传一个参数表示是获取 or 修改节点值就可以。
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
- 通过二叉搜索树的性质，可得链表的中间节点就是二叉树的根节点。使用快慢指针，慢指针每次移动一个节点，快指针每次移动两个节点，当快节点达到末尾时慢指针就到中间节点。对于一个偶数长度的链表，中间两个元素都可用来作二叉搜索树的根。找到中加节点后，把链表从中间断开成左右两部分（即树的左右子树），以此递归即可。需要使用一个变量来保存中间节点的前一个节点，将其 next 指向 null 就是左子树了。
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。
示例：
输入：
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
解释：
节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。
提示：
你必须返回给定头的拷贝作为对克隆列表的引用。
-
先循环一遍链表，使用 map 缓存链表的各个结点，以节点为键，以一个新节点为值。再循环一遍链表，根据当前节点的 next 从 map 中取出对应的新节点，重新给节点的 next 赋值。但这方法是 O(n)的空间复杂度，O(n)的时间复杂度。
-
使用三次while循环。O(1)的空间复杂度，O(n)的时间复杂度。《剑指offer》第187页。
- 第一次在原链表上增加复制的结点，如: 1->1
->2->2->3->3`->4->4。 - 第二次循环给复制的结点的random赋值，可以直接定位到原结点.random.next，即为要赋值结点的random。
- 第三次循环截取出复制的链表，如 1
->2->3->4，即为所求。
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。（示意图看原题）
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
-
快慢指针。慢指针每次走一个节点，快指针每次走两个节点。如果快指针和慢指针在中途相遇则说明有环。
-
遍历链表，使用 map 存储每一个节点。如果当前节点在 map 中已经存在则有环，不存在的话则存进 map 中。
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
-
快慢指针。先使用快慢指针找出是否有环。有环的话，假设链表起点到入环起点的距离是 a，入环起点到快慢指针交点的距离是 b。因为快指针走过的距离一直都是慢指针的两倍，所以整个环的长度减去 b = a（即交点再到入环起点的距离是 a）。所以只要再让一个指针从链表起点和原先的慢指针同步走，两者相等时就是入环起点（因为两者走的距离都是 a）。
-
先遍历一遍，使用 map 存储每个节点的值，如果当前节点已经在 map 中出现（即环的起点），则给该节点设一个标记值。之后在循环一次链表，找到该标记值返回当前节点即可。
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
-
双向链表。先循环一遍链表，维护一个 pre 使链表成为双向链表（pre初始为 null，最终为链表的最后一个节点）。之后再循环链表，通过 pre 往回得到前一个节点，插在链表当中。需要注意的是循环的次数是链表长度的一半，且最后一次循环时需要把链表尾部指向null，把剩下的节点裁剪掉。
-
使用数组缓存。先循环一遍链表存下每个节点。之后再根据数组将相应的节点插入链表中。
-
先深拷贝一次链表（递归拷贝），再翻转该拷贝的链表。把翻转后的链表节点插入原链表即可。
对链表进行插入排序。插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
- 相当于选择排序。将当前节点和已好排序的链表中的每一个节点比较大小并插入。需注意的是刚开始遍历时已排好序的链表为空，以及若已排序链表的第一个节点值大于当前节点，这两种情况下是将当前节点插入到已排序链表的首部。
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
-
同数组的选择排序。
-
先使用数组存储链表中的节点值，对数组进行 sort 排序。再遍历链表给节点值重新赋值。
编写一个程序，找到两个单链表相交的起始节点。
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
- 先获取两个链表的长度，让较长的链表先移动直至剩下的链表长度和另一个链表长度相等。再同时遍历两个链表，判断当前的节点是否相等，是的话则是交点。
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
-
直接遍历链表。但需要注意对头节点做特殊处理，对于头节点不是改变 cur.next, 而是直接修改 cur 和 head。
-
递归。
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
-
从第一个节点开始遍历，维护一个 pre 变量（初始化为 null）即可。
-
递归。将下一个节点的 next 修改为 当前节点 head，head 的 next 修改为 null。
-
使用数组缓存每个节点值，从数组尾部开始给每一个节点赋值。
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
-
数组缓存每个节点。将数组转化为字符串，和翻转后的数组字符串化比较。
-
双向链表。先给链表的每一个节点增加一个 pre 属性。同时从头到尾和从尾到头比较当前节点值是否相等。
-
先深拷贝链表，再翻转链表，之后遍历两个链表，比较两者的当前节点值。
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
- 直接修改待修改节点 的 val 和 next 就可以了。
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
-
维护奇偶两条链表，遍历原先的链表将奇偶节点各自增加到相应的链表上，最后将偶链表拼接在奇链表上即可。
-
先将链表的值存到数组中。再遍历链表修改当前节点的值。
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7
- 先翻转两个链表，再逐个节点相加。维护一个 ans 和 pre 变量。ans 为当前的结果，pre 为上次的结果。因为高位是在链表头，所以每次都把 ans 的 next 指向 pre 即可。需要注意两个链表可能不等长，当前节点可能为空，为空直接使当前的节点值为0即可。以及可能循环完毕后还有一个进位，所以最后还需要再处理下进位的问题。
给定一个头结点为 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.前面部分的长度大于等于后面部分的长度。
- 先计算链表长度len，len / k 即每个子链表的最小长度，len % k 即剩下还有多少个节点。如果剩下的节点数大于0的话，则先给前面的子链表多增加一个节点，直至剩下的节点数为0。当子链表长度达到要求后就放入数组中，重新开始。需要注意的是最后得到的子链表数可能小于k，需要在数组中用 null 补充。
您将获得一个双向链表，除了下一个和前一个指针之外，它还有一个子指针，可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
扁平化列表，使所有结点出现在单级双链表中。您将获得列表第一级的头部。
示例:
输入:
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL
输出: 1-2-3-7-8-11-12-9-10-4-5-6-NULL
- 遍历链表，若当前节点有child则先把原链表的next保存到一个数组头部，并把当前节点的child置空，将当前节点的 next 指向 child。 等所有的child都添加到链表上后再从数组中取出之前保存的链表剩余部分继续拼接。需要注意的是，当拼接完最底层的链表后，此时当前节点的 next 为空，但数组中还有未拼接的链表，所以需要对这种情况做判断并处理。
给定一个链表（链表结点包含一个整型值）的头结点 head。同时给定列表 G，该列表是上述链表中整型值的一个子集。返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。
示例 1：
输入:
head: 0->1->2->3
G = [0, 1, 3]
输出: 2
解释:
链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。
示例 2：
输入:
head: 0->1->2->3->4
G = [0, 3, 1, 4]
输出: 2
解释:
链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。
- 先使用 map/对象 标记链表中每一个节点在列表 G 中是否存在。遍历链表，维护两个变量，一个标记组件是否开始，一个标记当前节点是否存在列表中。组件开始后若当前节点不在列表中，则组件数加1。需要注意的是链表循环结束后可能组件还没结束，此时组件数需要再加1。
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
-
快慢指针，慢指针移动的距离是快指针的一半。
-
双向链表。
-
通过链表长度来取中间结点。
给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。
注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
示例 1：
输入：[2,1,5]
输出：[5,5,0]
- 类似于选择排序。先把链表中的节点值保存到一个数组中。
给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。删除完毕后，请你返回最终结果链表的头节点。
你可以返回任何满足题目要求的答案。（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）
示例 1：
输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。
示例 2：
输入：head = [1,2,3,-3,4]
输出：[1,2,4]
示例 3：
输入：head = [1,2,3,-3,-2]
输出：[1]
- 计算各个节点的前缀和。对于前缀和相同的项，说明这两个节点之间的和为0，可以消除他们中间的数（包括第二个节点的数）。用map来记录每个前缀和对应的链表节点。有重复的前缀和，就将上一个相同前缀和的节点的next指向当前相同前缀和的节点的next。需要注意的是：
- 拼接next前需要将记录他们中间的数的map清空，以免对之后的判断造成影响。
- 链表可能是
0 -> null，所以需要建一个虚拟节点（0），将其next指向head，这样可以先将0记录在map中。 - 链表可能是
0 -> 0 -> null，按上述步骤删除掉第一个0后，会清出map对0的记录，这时虚拟节点（0）的记录也被清空了，所以清空完成相应的map后，还需要把当前的前缀和记录为上一个节点。
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
- 假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数，则
G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)。当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，则f(i) = G(i-1)*G(n-i)。综合两个公式可以得到卡特兰数公式G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)。
给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例:
输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
- 递归。编写一个生成 start...end 为根节点所组成的二叉搜索树的函数。循环分别以 start...end 为根节点，则其左右子树范围分别为 [start, i-1] 和 [i+1, end]，递归左右子树得到左右子树的所有可能。把左右子树数组两两搭配作为当前根节点的左右子树，存进数组中。最后即可得到所有由 1 ... n 为节点所组成的二叉搜索树。
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
- 二叉搜索树的中序遍历的结果就是升序的，所以只要中序遍历一遍，比较当前节点和数组中它的前一个节点的大小即可。
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
- 递归比较两棵树的左右子树。递归终止条件是两棵树都为null或其中一个为null或两棵树的节点值不相等。
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
- 递归。把一棵树抽象成两棵 l 和 r，对称的话则 l.left 和 r.right 、l.right, r.left 是相等的。递归代码大致同上题。
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
- 递归左右子树，每次递归后比较左右子树的深度大小，在其基础上加1返回做回本层的深度。
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
- 先序遍历的第一个节点就是根节点，所以遍历中序遍历找出根节点的位置，通过根节点在中序遍历中的索引 index 即可得到左右子树各自所包含的节点数（左子树的节点是 index - inL）。则左右子树各自的前序中序遍历位置为
(preL+1, preL+leftNum, inL, index-1)，(preL+leftNum+1, preR, index+1, inR)递归构建左右子树即可。
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
- 思路同上，只是根节点换做了后序遍历的最后一个节点。找出根节点在中序遍历中的索引后，左右子树各自的中序后序遍历位置为
(l1, index - 1, l2, l2 + sum - 1)，(index + 1, r1, l2 + sum, r2 - 1)。
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
- 数组的中间节点就是这个二叉搜索树的根节点，其数组索引是
l + Math.floor((r - l) / 2)，递归构建左右子树就可以了。
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
- 先编写求树深度的函数，得到左右子树的深度。若左右子树平衡的话，则递归判断左右子树内部是否也平衡。
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
- 递归获取左右子树。如果左右子树的深度都不为0的话，则取最小值 + 1（加1是算上根节点）。若有一个或两个都为0的话，则取
1 + left + right。
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
- 可以先假设一颗空树、只有根结点的树、只有一个根节点和一个叶子结点的树，假设出几颗树后根据这些情况编写递归式和终止条件。递归左右子树，每次递归左右子树时把 sum 减去当前根节点的值即可。
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
- 编写一个用来递归的函数，接受三个参数分别是根节点root、目标和sum 和当前的路径数组。每次都把当前的节点存入路径数组中，再以当前路径递归其左右子树。如果当前节点左右子树为空且节点值等于目标和，则路径成立。此时需要把当前的路径数组拷贝一份后再放入结果数组中，否则会影响到后续操作，并且把的当前的节点值pop出路径数组，才好回溯寻找其他路径。
给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为：
1
\
2
\
3
\
4
\
5
\
6
- 分为三个过程：1.左子树插入到右子树的地方。 2.将原来的右子树接到左子树的最右边节点。3.继续迭代右子树。
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。
-
自顶向下递归。左孩子的next都是父节点的右孩子。若父节点的next存在，则右孩子的next是其父节点的next的左孩子，不存在的话则是null。以此递归左右子树。
-
相当于层次遍历。用一个数组存储当前层次的所有节点，先使用一个变量sum标记当前层次的的节点数量。若遍历到当前节点时，sum不为0，则其next是数组中的第一个节点，否则为null。
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。
- 层序遍历存储遍历的顺序，使用 next 代替 queue进行层序遍历。
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
- 思路类同于寻找二叉树的所有路径，在递归左右子树前把当前路径的数字和 sum * 10 + root.val。并在叶子节点时将 sum 加入结果 res 后，sum需要减去当前节点的值以便回溯其他路径的数字和。
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。调用 next() 将返回二叉搜索树中的下一个最小的数。
示例：
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false
提示：
next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。
- 二叉搜索树进行中序遍历就是升序序列。
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
-
深度递归。先递归右子树，再递归左子树，保证右边的节点会先被看到。dfs函数维持一个变量 deep，表示当前遍历的深度。如果 deep 大于结果数组的长度，则将当前的节点加入结果数组中。这样可以保证同一层级上，右子树和左子树只会有一个被看到，即先到先得。
-
层次遍历。只把每一层最后一个节点加入结果数组中。
给出一个完全二叉树，求出该树的节点个数。
说明：完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例:
输入:
1
/ \
2 3
/ \ /
4 5 6
输出: 6
-
递归。
-
完全二叉树是一棵空树或者它的叶子节点只出在最后两层，若最后一层不满则叶子节点只在最左侧。
- 先计算左右子树的高度，如果两者高度不相等，说明最后一层不满，并且右子树是满二叉树。此时可以通过公式（2^h - 1）直接得到右子树的节点数，左子树则递归获取。
- 如果两者高度相等，说明左子树是满二叉树。此时可以通过公司直接得到左子树的节点数，右子树则递归获取。
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
- 递归左右子树，并保存递归后的结果，再调换当前节点左右子树的值。
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
-
对于二叉搜索树，中序遍历后的序列就是二叉树的升序序列。
-
使用一个变量记录结果，每次递归完左子树后就记录当前的节点，并使k--，如果
k <= 0 || root === null则退出递归。
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
- 如果当前的根节点值小于p大于q，说明p和q分别在当前节点的左右子树上，所以当前节点就是它们的公共祖先。如果都小于p的话，说明p和q都在左子树上，则递归左子树。如果都大于q的话，说明p和q都在右子树上，则递归右子树。
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
- 递归左右子树，并使用两个变量保存递归结果。如果两个变量都有值，说明p和q分别在左右子树上，则root是她们的最近公共祖先。如果只有左子树有值右子树值为null，说明p和q都在左子树上。
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
- 递归。递归函数传一个字符串表示当前的路径，在叶子节点时将其加入结果数组中就行。
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
-
DP。维护一个数组，分别存储盗取当前节点和不盗取当前节点的最高金额，每次递归都返回这个数组。不包含当前节点的话，则最高金额是左子树能获取的最高金额（同样是区分是否盗取左子树根节点）与右子树能盗取的最大金额之和。包含当前节点的话，则最高金额是不盗取左右子树根节点能获取的金额再加上当前节点的金额。通过递归获取底层节点能获取到的最高金额，最后便能得到整个二叉树所能获得的最高金额。
-
思路同上，只是不使用一个数组去记录，而是直接递归求出每种情况下所能获取的金额。
计算给定二叉树的所有左叶子之和。
示例：
3
/ \
9 20
/ \
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
- 递归。递归左右子树的时候，参数使用一个变量 mark 来标记当前的递归是左子树还是右子树。如果是左子树并且是叶子节点则累加结果值。
给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过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
- 使用两次递归。一次递归遍历每一个结点，再以当前的结点作为根节点，递归向下寻找路径数。
序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
- 普通的二叉树需要 前序遍历+中序遍历 或者 后序遍历+中序遍历 才能够确定一棵树，但二叉搜索树只需要前序遍历就能够确定了，小于根节点的都是左子树，大于根节点的都在右子树。在构建二叉搜索树时，只需要找到第一个大于根节点的数的索引（即右子树开始的地方）就可以确定左右子树的范围了，并以此递归就行。（本题未AC）
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
示例:
root = [5,3,6,2,4,null,7]
key = 3
5
/ \
3 6
/ \ \
2 4 7
给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
5
/ \
4 6
/ \
2 7
另一个正确答案是 [5,2,6,null,4,null,7]。
5
/ \
2 6
\ \
4 7
- 要删除二叉搜索树中的节点，需要找到仅小于(左子树中最右边的节点)或仅大于(右子树中最左边的节点)待删除节点的节点，修改它的左右子树指向并返回给上层节点充当它的左(右)子树。需要注意的是要断开替换节点和它父节点(使用一个parnent变量来记录)的联系，否则拼接子树的时候可能会出现环，导致本题报堆溢出的错误。
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],
1
\
2
/
2
返回[2].
提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
-
中序遍历，使用哈希记录，但空间复杂度比较大。
-
记录最大出现次数、当前节点值的出现次数、上一个节点的值。如果当前节点值出现次数等于最大出现次数，则直接加入结果数组；如果大于最大出现次数，则清空结果数组后再加入结果数组。
给出二叉树的根，找出出现次数最多的子树元素和。一个结点的子树元素和定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。然后求出出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的元素（不限顺序）。
示例 1
输入:
5
/ \
2 -3
返回 [2, -3, 4]，所有的值均只出现一次，以任意顺序返回所有值。
示例 2
输入:
5
/ \
2 -5
返回 [2]，只有 2 出现两次，-5 只出现 1 次。
- 计算子树元素和，应该自底向上，这样可以得到自底向上得到每个节点的元素和，也就是要后续遍历。递归左右子树可以得到左右子树的元素和，加上当前节点值即可得到当前节点的元素和。将得到的每个节点的元素和记录在一个对象中（使用数组是因为既要使用记录元素和，也要记录出现的次数），遍历这个对象边比较出现次数的最大值，边维护结果数组。
给定一个二叉树，在树的最后一行找到最左边的值。
示例 1:
输入:
1
/ \
2 3
/ / \
4 5 6
/
7
输出: 7
-
比较左右子树哪个更深，每次都在深度更大的子树里面找，深度相等的话则在左子树里找。判断收否是叶子节点并返回即可。
-
中序遍历（从左往右）。维护一个最大深度并以此更新结果值。
您需要在二叉树的每一行中找到最大的值。
示例：
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: [1, 3, 9]
- 层序遍历，记录每层的最大值
给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。
示例 :
输入:
1
\
3
/
2
输出:1
解释:
最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
注意: 树中至少有2个节点。
- 中序遍历就是升序，比较相邻两个节点的值（使用一个变量来存储上一个节点值）。
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如：
输入: 二叉搜索树:
5
/ \
2 13
输出: 转换为累加树:
18
/ \
20 13
- 从右节点 -> 根节点 -> 左节点（从大到小），使用一个变量记录累加和。
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
- 左子树的深度+右子树的深度+根节点 = 一条路径的节点个数，边数等于路径上节点数-1。
给定一个二叉树，计算整个树的坡度。
一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。
示例:
输入:
1
/ \
2 3
输出: 1
解释:
结点的坡度 2 : 0
结点的坡度 3 : 0
结点的坡度 1 : |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1
- 递归。计算每个节点的坡度，累加到结果数中，并给父节点返回它的子树和。
给定两个非空二叉树 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。
-
直接字符串化两棵树，判断t树是否出现在s树的字符串中。
-
递归s树，对于递归中的每个节点，去比较它和t树的节点值是否相等，相等的话则递归比较两者的左右子树。
你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1:
输入: 二叉树: [1,2,3,4]
1
/ \
2 3
/
4
输出: "1(2(4))(3)"
解释: 原本将是“1(2(4)())(3())”，
在你省略所有不必要的空括号对之后，
它将是“1(2(4))(3)”。
示例 2:
输入: 二叉树: [1,2,3,null,4]
1
/ \
2 3
\
4
输出: "1(2()(4))(3)"
解释: 和第一个示例相似，
除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。
- 分四种情况进行递归：没有左右子树、只有右子树、只有左子树、左右子树都有。
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。
- 递归。如果有一棵树为空，则给上层返回另一棵非空的树。若两棵树都非空，则节点值进行合并，左右子树再递归合并。
给定一个二叉树，根节点为第1层，深度为 1。在其第 d 层追加一行值为 v 的节点。
添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，为 N 创建两个值为 v 的左子树和右子树。
将 N 原先的左子树，连接为新节点 v 的左子树；将 N 原先的右子树，连接为新节点 v 的右子树。
如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。
示例 1:
输入:
二叉树如下所示:
4
/ \
2 6
/ \ /
3 1 5
v = 1
d = 2
输出:
4
/ \
1 1
/ \
2 6
/ \ /
3 1 5
注意:
输入的深度值 d 的范围是：[1，二叉树最大深度 + 1]。
输入的二叉树至少有一个节点。
- 递归。递归到d-1层，修改d-1层根节点的左右子树。
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
示例 1:
输入:
3
/ \
9 20
/ \
15 7
输出: [3, 14.5, 11]
解释: 第0层的平均值是 3, 第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
注意：节点值的范围在32位有符号整数范围内。
- 只是层次遍历。
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。两棵树重复是指它们具有相同的结构以及相同的结点值。
示例 1：
1
/ \
2 3
/ / \
4 2 4
/
4
下面是两个重复的子树：
2
/
4
和
4
因此，你需要以列表的形式返回上述重复子树的根结点。
- 使用map。以序列化的树作为键，出现的次数作为值记录进map中。同样是字符串化树，但使用 JSON.stringify 耗时比较多，所以直接使用拼接字符串。
给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
案例 1:
输入:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
输出: True
-
将BST中序遍历成一个升序的数组，使用前后指针求解。
-
遍历二叉树，对于每一个节点node，再递归寻找树中是否存在值为target-node.val的节点
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。
示例 ：
输入：[3,2,1,6,0,5]
输出：返回下面这棵树的根节点：
6
/ \
3 5
\ /
2 0
\
1
- 类似于先(后)序遍历+中序遍历构建二叉树。
在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：
行数 m 应当等于给定二叉树的高度。
列数 n 应当总是奇数。
根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。
每个未使用的空间应包含一个空的字符串""。
使用相同的规则输出子树。
示例 1:
输入:
1
/
2
输出:
[["", "1", ""],
["2", "", ""]]
示例 2:
输入:
1
/ \
2 3
\
4
输出:
[["", "", "", "1", "", "", ""],
["", "2", "", "", "", "3", ""],
["", "", "4", "", "", "", ""]]
- 先计算出树的深度和节点个数，以此初始化一个二维数组。再遍历二叉树，类似于构造二叉树，通过左右子树的索引范围递归填充二维数组（使用到一个变量来标记当前节点的深度）。
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
示例 1:
输入:
1
/
3
/ \
5 3
输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
示例 2:
输入:
1
/ \
3 2
/
5
输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
- 给每个节点编号，从1开始，只将每层最左边的节点编号加入到数组中，则arr[i-1]是第i层最左边节点的编号。将当前的节点编号减去arr[i-1]就是当前的宽度，和最大宽度比较并不断更新即可
给定一个二叉搜索树，同时给定最小边界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
- 递归。若当前的节点值小于L，说明新节点在右子树，则返回右子树给上层上层。若大于R，则返回左子树给上层，否则返回原节点给上层。
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。
给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
示例 1:
输入:
2
/ \
2 5
/ \
5 7
输出: 5
说明: 最小的值是 2 ，第二小的值是 5 。
示例 2:
输入:
2
/ \
2 2
输出: -1
说明: 最小的值是 2, 但是不存在第二小的值。
- 递归。最小的节点是根节点，所以第二小的节点是第一个大于根节点的节点。因为子节点的值不小于根节点的值，所以递归查找左右子树。
在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
示例 1：
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
1
/ \
2 - 3
示例 2：
输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
| |
4 - 3
- 并查集。去掉冗余边后树就不连通了，所以在连通的树中，可以通过其中一条边找到其他的边。所以可以给每个节点标记一个父节点，表示该节点最终可以到达的节点。如果有一条边，两个节点的父节点相等，也就是它们都可以到达该父节点（形成环了），则该边是冗余边。
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出: 2
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出: 2
- 递归。计算左右子树中同值路径的长度，并返回其中较大的给上一层。注意不能直接返回子树递归得到的长度l/r，而是要重新定义变量表示当前节点的同值路径长度lSum和rSum，如果当前节点值等于子树节点值，则更新lSum/rSum。若是直接返回l/r，祖先节点会收集到子树中所有同值的路径长度，比如孙节点有一个同值(1)路径长度是2，孙孙节点有一个同值(11)路径长度是3，则2和3都会加到l/r上。所以需要重新定义lSum和rSum，表示当前节点的同值路径长度，避免累加上子树的同值路径节点。
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
-
就是层次遍历而已。
-
递归，递归函数使用一个参数来表示当前的深度即可。
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
说明:
树的深度不会超过 1000。
树的节点总不会超过 5000。
- 递归。跟求二叉树最大深度差不多，递归函数维持一个变量表示当前的深度，并更新最大深度即可。
给定一个 N 叉树，返回其节点值的前序遍历。
- 大致同二叉树的前序遍历，分为递归和迭代。注意迭代只能使用 unshift，而不能使用 push 才能保证左子树会先于右子树被访问到。
给定一个 N 叉树，返回其节点值的后序遍历。
- 同上题。区别在于上题是 push(node.val)，本题是 unshift(node.val) 得到的才是后序遍历。
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
例如，
给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和值: 2
你应该返回如下子树:
2
/ \
1 3
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
- 常规递归。根据当前节点的值和val的大小关系，选择递归左/右子树或者直接返回当前的节点。
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
例如,
给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和 插入的值: 5
你可以返回这个二叉搜索树:
4
/ \
2 7
/ \ /
1 3 5
或者这个树也是有效的:
5
/ \
2 7
/ \
1 3
\
4
- 根据当前节点值和val的大小关系，更新左/右子树。
给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
示例：
输入: root = [4,2,6,1,3,null,null]
输出: 1
解释:
注意，root是树结点对象(TreeNode object)，而不是数组。
给定的树 [4,2,6,1,3,null,null] 可表示为下图:
4
/ \
2 6
/ \
1 3
最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。
- BST中序遍历就是升序了，所以只需要在中序遍历中使用一个变量记录上一个值，将它与当前节点值之差和res比较并维护即可。
给定二叉树根结点 node ，此外树的每个结点的值要么是 0，要么是 1。
返回移除了所有不包含 1 的子树的原二叉树。
( 节点 X 的子树为 X 本身，以及所有 X 的后代。)
- 递归。递归判断左右子树，根据其子树的返回值选择是否将子树值为null。
给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。
返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。
注意，输入的 "root" 和 "target" 实际上是树上的结点。
提示：
给定的树是非空的，且最多有 K 个结点。
树上的每个结点都具有唯一的值 0 <= node.val <= 500 。
目标结点 target 是树上的结点。
0 <= K <= 1000.
- 递归。使用map记录节点的父节点，用来向上寻找节点。从target开始，向左子树、右子树、父节点开始搜索，但需要记录节点是否访问过，否则访问完子树后，又递归找子树的父节点，导致记录到target节点。
给定一个根为 root 的二叉树，每个结点的深度是它到根的最短距离。
如果一个结点在整个树的任意结点之间具有最大的深度，则该结点是最深的。
一个结点的子树是该结点加上它的所有后代的集合。
返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。
- 递归。相当于找叶子节点深度相等的最深根节点。递归左右子树中比较高的那颗子树，高度相等的话则返回根节点。
请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false。
- 先序遍历，记录叶子节点后比较即可。
返回与给定的前序和后序遍历匹配的任何二叉树。pre 和 post 遍历中的值是不同的正整数。
示例：
输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]
提示：
1 <= pre.length == post.length <= 30
pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列
每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。
- 大致同前/后+中序遍历构建二叉树。后续遍历中倒数第二个元素是右子树的根节点。所以先循环前序遍历序列，找到该根节点的索引为rightIndex，因此可以算出左子树的节点个数是rightIndex-1-l1,进一步可得左右子树的范围。
满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。
返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。
答案中每个树的每个结点都必须有 node.val=0。
你可以按任何顺序返回树的最终列表。
- 满二叉树的节点数只能是奇数，且如果N为1的话得到的满二叉树只有根节点。假设左子树有leftTreeSum个节点，则右子树有N-1-leftTreeSum个节点。每次递归时都将leftTreeSum+2，将得到的左右子树组合分配并放入结果数组中返回给父节点。
给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
示例 ：
输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]
5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9
-
先序遍历获取节点值存到数组中，再拼接二叉树。
-
中序遍历，类似链表连接，用一个变量cur表示当前的节点，修改它的左节点和右节点指向。
完全二叉树是每一层（除最后一层外）都是完全填充（即，结点数达到最大）的，并且所有的结点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：
CBTInserter(TreeNode root) 使用头结点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v) 将 TreeNode 插入到存在值为 node.val = v 的树中以使其保持完全二叉树的状态，并返回插入的 TreeNode 的父结点的值；
CBTInserter.get_root() 将返回树的头结点。
题目意思：在一棵完全二叉树中插入一个节点，使插入后的二叉树还是完全二叉树。
-
因为是完全二叉树，所以使用层序遍历，当遍历到第一个没有左/右节点的节点时，就将新节点插在它的左/右节点上。
-
给每个节点编号（也就是存入数组中），类似于堆，根据编号找到父节点的位置。
给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。二叉搜索树保证具有唯一的值。
示例 1：
输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
输出：32
示例 2：
输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
输出：23
题意：累加树中所有节点值大于等于L小于等于R的节点值。
- 递归。先底向上返回底层的结果最终累加给根节点。当前节点值小于L，则只需要递归右子树；当前节点值大于R，则只需要递归左子树。若L<=当前节点值<=R，则返回左右子树的递归结果+当前的节点值给上层。
我们可以为二叉树 T 定义一个翻转操作，如下所示：选择任意节点，然后交换它的左子树和右子树。
只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转等价于二叉树 Y。
编写一个判断两个二叉树是否是翻转等价的函数。这些树由根节点 root1 和 root2 给出。
- 如果当前根节点相等，则不用继续比较直接返回true。如果根节点只有一个为null或者两个根节点值不相等，则直接返回false。否则按当前树的状态递归，和翻转后（左子树和右子树比较，右子树和左子树比较）递归，对两者的递归结果取或即可。
给定一个二叉树，确定它是否是一个完全二叉树。
- 层序遍历。使用一个变量finished标记是否已经遇到空节点。finished为true后若还遇到空节点说明不是完全二叉树。
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
-
把当前节点的值传给递归函数，比较每个节点的值和根节点的值是否都相等。
-
将当前节点值和左右子树值比较。
给定一个有 N 个节点的二叉树，每个节点都有一个不同于其他节点且处于 {1, ..., N} 中的值。
通过交换节点的左子节点和右子节点，可以翻转该二叉树中的节点。
考虑从根节点开始的先序遍历报告的 N 值序列。将这一 N 值序列称为树的行程。
（回想一下，节点的先序遍历意味着我们报告当前节点的值，然后先序遍历左子节点，再先序遍历右子节点。）
我们的目标是翻转最少的树中节点，以便树的行程与给定的行程 voyage 相匹配。
如果可以，则返回翻转的所有节点的值的列表。你可以按任何顺序返回答案。
如果不能，则返回列表 [-1]。
- 使用变量finished标记是否有匹配，index表示遍历到voyage的当前索引。比较当前的根节点，如果和voyage[index]不相等则表示不匹配。如果左节点值不等于voyage[index+1]而右节点值等于voyage[index+1]，说明可以通过翻转得到匹配的序列。如果左节点值和右节点值都不等于voyage[index+1]，说明无法通过翻转得到正确序列，不匹配。其他情况下则递归判断左右节点
给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。
在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。
返回使每个结点上只有一枚硬币所需的移动次数。
输入：[0,3,0]
输出：3
解释：从根结点的左子结点开始，我们将两枚硬币移到根结点上 [移动两次]。然后，我们把一枚硬币从根结点移到右子结点上。
- 递归。从底向上，每次都给父节点返回子树的过载量（超出/缺少多少枚硬币），累加左右子树的过载量即可。注意在累加过载量时需要取绝对值，因为过载量可能是负的。
给定二叉树，按垂序遍历返回其结点值。
对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。
把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（ Y 坐标递减）。
如果两个结点位置相同，则首先报告的结点值较小。
按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。
输入：[3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：
在不丧失其普遍性的情况下，我们可以假设根结点位于 (0, 0)：
然后，值为 9 的结点出现在 (-1, -1)；
值为 3 和 15 的两个结点分别出现在 (0, 0) 和 (0, -2)；
值为 20 的结点出现在 (1, -1)；
值为 7 的结点出现在 (2, -2)。
- 先递归计算出每个节点的坐标存入数组arr中。根据垂序遍历的规则，对arr进行排序：y坐标小的放前面；y坐标相同x坐标不同，则x坐标小的在前面；x坐标和y坐标都相同则节点值小的在前面。排完序后根据数组中y坐标不同分做二维数组输出即可。
给定一颗根结点为 root 的二叉树，书中的每个结点都有一个从 0 到 25 的值，分别代表字母 'a' 到 'z'：值 0 代表 'a'，值 1 代表 'b'，依此类推。
找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
（小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。）
- 递归。记录从根节点到叶子节点的各条路径后，翻转路径序列变成从叶子节点到根节点，和结果序列比较大小。
在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。
- 记录首先遇到的目标节点的父节点值和深度值，父节点值和深度值作为递归函数的参数传递。
最大树定义：一个树，其中每个节点的值都大于其子树中的任何其他值。
给出最大树的根节点 root。
就像之前的问题那样，给定的树是从表 A（root = Construct(A)）递归地使用下述 Construct(A) 例程构造的：
如果 A 为空，返回 null
否则，令 A[i] 作为 A 的最大元素。创建一个值为 A[i] 的根节点 root
root 的左子树将被构建为 Construct([A[0], A[1], ..., A[i-1]])
root 的右子树将被构建为 Construct([A[i+1], A[i+2], ..., A[A.length - 1]])
返回 root
请注意，我们没有直接给定 A，只有一个根节点 root = Construct(A).
假设 B 是 A 的副本，并附加值 val。保证 B 中的值是不同的。返回 Construct(B)。
- 如果val小于根节点值，则将新节点插入右子树中递归判断。反之则将新节点作为根节点，原树作为新节点的左子树。
返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
-
将先序遍历升序排序得到中序遍历（平衡二叉树的中序遍历是升序的），题目转化为由先序遍历和中序遍历构造二叉树。
-
因为该先序遍历也是平衡二叉树的先序遍历序列，所以第一个大于根节点的值就是右子树开始的地方，它后面的值也都大于根节点。以此划分左右子树的范围。
给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
以 10^9 + 7 为模，返回这些数字之和。
- 递归。相当于寻找所有根节点到叶子节点的路径。每下一层，就将已经过路径的数字和乘2，在叶子节点累加结果即可。
给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
-
递归。自顶向下，向子孙节点传递它祖先节点中最大和最小的节点，将当前的节点值分别和两者求最大差值，记录维护这个最大差值就可。
-
还是递归。和第一种解法的区别在于，此解是先走完整条路径，找出最大节点和最小节点，等到了叶子节点后再计算路径上最大最小值之差。
在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。
示例 1：
输入：label = 14
输出：[1,3,4,14]
- 迭代。如果按照原来满二叉树的性质来，节点 label 的父节点是节点 Math.floor(label/2)。观察得到现在节点label的父节点和节点 Math.floor(label/2)是对称的，所以可以通过这个对称的性质计算得到现在的父节点。现在的父节点 = 父节点层的起始节点 + 从第一层到父节点层的所有节点数 - 原来的父节点Math.floor(label/2) = 父节点层的起始节点 + 父节点层的节点数 * 2 - 1 - Math.floor(label / 2))。
给出二叉树的根节点 root，树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
返回森林中的每棵树。你可以按任意顺序组织答案。
示例：
输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出：[[1,2,null,4],[6],[7]]
- 递归。如果当前节点是要删除的话，则判断是否是叶子节点，是叶子节点的话直接返回null给父层用于断开两者之间的连接。如果不是叶子节点的话，则递归判断左右子树，并同样也返回null给父层。如果递归返回的结果不是空的话（子树中有有效的节点，如果不对递归结果判断的话，可能得到的子树是空树，导致把空树也加入res中了），则加入结果数组res中。（对于这种会修改二叉树结构的，递归函数需要返回一个值给父层，才能修改父节点的子树从而修改二叉树）
给你一个有根节点的二叉树，找到它最深的叶节点的最近公共祖先。
示例 1：
输入：root = [1,2,3]
输出：[1,2,3]
示例 2：
输入：root = [1,2,3,4]
输出：[4]
- 递归。如果左右子树深度相等，则当前节点就是最深叶子节点的最近公共祖先，反之在深度更大的子树上。如果只有一个最深的叶结点，那么它的最近公共祖先就是它自己
给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：
每个节点都有 0 个或是 2 个子节点。
数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。（知识回顾：如果一个节点有 0 个子节点，那么该节点为叶节点。）
每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。
示例：
输入：arr = [6,2,4]
输出：32
解释：
有两种可能的树，第一种的非叶节点的总和为 36，第二种非叶节点的总和为 32。
24 24
/ \ / \
12 4 6 8
/ \ / \
6 2 2 4
- 把叶子节点划分区间给左右子树，计算出当左/右子树的叶子节点区间在 [start, end] 之间时子树的最小代价生成树（使用一个二维数组记录避免重复计算）。每次递归都返回当前根节点的最小生成代价树作为父节点的子树结果，最后递归的结果就是整棵树的最小代价生成树。
有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。
游戏从「一号」玩家开始（「一号」玩家为红色，「二号」玩家为蓝色），最开始时，
「一号」玩家从 [1, n] 中取一个值 x（1 <= x <= n）；
「二号」玩家也从 [1, n] 中取一个值 y（1 <= y <= n）且 y != x。
「一号」玩家给值为 x 的节点染上红色，而「二号」玩家给值为 y 的节点染上蓝色。
之后两位玩家轮流进行操作，每一回合，玩家选择一个他之前涂好颜色的节点，将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色。
如果当前玩家无法找到这样的节点来染色时，他的回合就会被跳过。
若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。
现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个 y 值可以确保你赢得这场游戏，则返回 true；若无法获胜，就请返回 false。
输入：root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
输出：True
解释：第二个玩家可以选择值为 2 的节点。
- 玩家一先选择了一个点涂色后，就把整个二叉树分成了三部分（左、右、父）。玩家二只能在这三部分中选择一个节点涂色，如果其中一部分的节点个数超过总节点数的一半（n / 2），即玩家二至少占据了一半的节点。那么玩家二可涂色的节点就比玩家一多，也就是玩家二必赢。所以问题就转换成了求x节点的左子树节点数、右子树节点数、父节点部分节点数（n - 左子树节点数 - 右子树节点数 - 1），这三个是否有一个大于总节点数的一半（n / 2）。
给出一个满足下述规则的二叉树：
root.val == 0
如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2
现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。
请你先还原二叉树，然后实现 FindElements 类：
FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。
- 常规递归。可以在初始化二叉树的时候，把每个节点值记录到一个对象里，这样在查找的时候就不用再遍历二叉树了。
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
- 每个数组元素为 item，先根据 item[0] 升序排序。循环数组判断 item[1] 和它的下一个数组元素 next[0] 的大小关系，大于等于就合并，合并后删除 next 以便合并后的区间和下一个区间继续比较（并且删除后需要
i--避免循环向前推进）。
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]
说明:
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
-
哈希。先用一个数组记录 nums1 中出现的元素，再循环 nums2 查找重复的元素。需要注意的是需要先使用 Set 去重，否则得到的结果中可能会有重复的元素。 时间复杂度 O(n + m)，空间复杂度 O(n)。
-
双指针。先给两个数组排序，然后使用 while 开始遍历两个数组，判断当前两个数组元素的大小关系，根据大小关系推进某个数组的循环变量。时间复杂度 O(nlogn + mlogm)，空间复杂度 O(1)
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
-
和
349. 两个数组的交集区别在于本题结果输出需要考虑到元素出现的次数，所以不用再使用 Set 去重。同样用哈希，不过需要记录元素出现的次数并做相应的调整。 -
双指针。同上。
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意:
数组长度不超过1000。
数组里整数的范围为 [0, 1000]。
-
暴力破解，三层 for 循环。如果没有事先排序的话则需要两两一组和另一个值比较大小。时间复杂度：O(N^3)
-
二分查找。先排序后两层 for 循环，通过二分查找找出数组中等于前两数之和的值的数组下标，它和第二个数之间的数组元素便满足两数之和大于第三个数。需要注意的是，这里二分查找要找的是数组中元素第一次出现的位置，因为元素可能重复出现。时间复杂度：O(N^2 * logN)
-
双指针。两层 for 循环后使用 while 推进判断
nums[i] + nums[j] > nums[t]，每次 j+1 后 t 不用从 j+1 开始算起，因为前面已经满足nums[i] + nums[j] > nums[t]，那么现在nums[i] + nums[j+1] > nums[t]也会成立。时间复杂度：O(N^2)
输入一个按升序排序的整数数组（可能包含重复数字），你需要将它们分割成几个子序列，其中每个子序列至少包含三个连续整数。返回你是否能做出这样的分割？
示例 1：
输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3
3, 4, 5
示例 2：
输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3, 4, 5
3, 4, 5
示例 3：
输入: [1,2,3,4,4,5]
输出: False
- 分别记录数组中每个元素出现的次数和以当前元素作为结尾的序列有多少个（可能有多个，比如数组为
[1,1,2,2,3,3]，这样以 3 为结尾的序列就有 2 个）。遍历数组，当前数组元素值为 val。如果存在以 val-1 结尾的序列，则将 val 增加到该序列中，并对两个记录数据做相应调整。不存在的话则判断是否存在 val+1 和 val+2，存在的话则可以另起一个新的序列，否则的话则表示 val 无法和其他数组元素连续起来，可以直接返回 false 了。
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
-
暴力破解，递归每次爬楼梯时的可能，爬 1 个台阶或爬 2 个台阶。
-
还是递归暴力破解，不过为了避免重复的递归计算，使用一个记忆数组记录已经计算过的值，可以把时间复杂度降到 O(n)。
-
dp，最好的情况就是在第 n-1 阶时跳 1 阶，或者在第 n-2 阶时跳 2 阶，以此类推计算前面的值即可得出 dp[n]。
-
斐波那契数列，从 dp 公式可以观察到本题就是求斐波那契数列中的第 n 项的值。
类似的爬楼梯还有这道。
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
- 对于任意数字 n，将 n 和 n-1 做与运算，都会把最后一个 1 的位变成 0。所以一直对两者做与运算，直至 n 变成 0 即可。
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
-
暴力破解，两层 for 算出两两组合的矩形面积。
-
双指针，一个在数组头，一个在数位尾。初始时底长已经是最大了，想要更大的面积，就只能寻找更大的边高。所以比较此时的两条边高，更小的那条舍弃，移动指针寻找下一条边看看能不能得到更大的面积。
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
-
哈希。记录每个数组元素出现的次数，判断哪个出现的次数大于 ⌊ n/2 ⌋。
-
排序。升序排序后，出现次数大于 ⌊ n/2 ⌋ 的那个数一定会出现在数组中间位置。
-
因为出现次数大于 ⌊ n/2 ⌋ 的元素，它出现的次数比其他所有数字出现的次数和还要多。所以可以维护两个数，一个表示数组元素 a（可以初始化为第一个数组元素），一个表示 a 出现的次数 sum。接着遍历数组，如果当前元素是 a 的话，就 sum++，否则就 sum--。如果当前的 sum 小于等于 0 的话，就将 a 改为记录当前的数组元素。最后得到的数组元素 a 一定是那个出现次数大于 ⌊ n/2 ⌋ 的数。
编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址。
IPv4 地址由十进制数和点来表示，每个地址包含4个十进制数，其范围为 0 - 255， 用(".")分割。比如，172.16.254.1；
同时，IPv4 地址内的数不会以 0 开头。比如，地址 172.16.254.01 是不合法的。
IPv6 地址由8组16进制的数字来表示，每组表示 16 比特。这些组数字通过 (":")分割。比如, 2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。所以， 2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 address地址 (即，忽略 0 开头，忽略大小写)。
然而，我们不能因为某个组的值为 0，而使用一个空的组，以至于出现 (::) 的情况。 比如， 2001:0db8:85a3::8A2E:0370:7334 是无效的 IPv6 地址。
同时，在 IPv6 地址中，多余的 0 也是不被允许的。比如， 02001:0db8:85a3:0000:0000:8a2e:0370:7334 是无效的。
说明: 你可以认为给定的字符串里没有空格或者其他特殊字符。
示例 1:
输入: "172.16.254.1"
输出: "IPv4"
解释: 这是一个有效的 IPv4 地址, 所以返回 "IPv4"。
示例 2:
输入: "2001:0db8:85a3:0:0:8A2E:0370:7334"
输出: "IPv6"
解释: 这是一个有效的 IPv6 地址, 所以返回 "IPv6"。
示例 3:
输入: "256.256.256.256"
输出: "Neither"
解释: 这个地址既不是 IPv4 也不是 IPv6 地址。
-
正则匹配。
-
按 ip 地址的格式要求一条条规则进行校验
IPV4：
- 由三个 . 间隔开分成四组
- 每组只能有数字字符且不能为空，且大于 0 小于等于 255
- 每组不能有前导 0
IPV6：
- 由七个 : 间隔开分组八组
- 每组只能是十六进制中允许的字符 0-9 或 a-f 或 A-F
- 每组不能为空，且长度不能大于 4
输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
- 将第一个元素和后面的元素都分别交换位置，并以此递归下去，就能得到全排列。类似的全排列还有这一题，区别在于一个输入是字符串，一个是数组，在交换元素位置上有区别。
有一个二维矩阵 grid ，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。
我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。
如果一座岛屿 完全 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。
请返回封闭岛屿的数目。
示例 1：
输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。
1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1
-
DFS。两层 for 循环遍历每一个格子，遇到岛屿的话就 DFS 递归每个方向是否封闭（先递归走完一个方向再走另一个方向）。只有四个方向都封闭这个岛屿才算是封闭岛屿，并且访问过的岛屿需要标记为已访问过，避免重复递归。需要注意的是，即使其中一个方向不是封闭的，也要递归完其他所有方向才行。
-
BFS。和 DFS 类似，不过 DFS 是一个方向递归到边界后再去递归另一个方向，而 BFS 是先遍历完一个岛屿的四个方向后，再去遍历另一个岛屿的四个方向，需要使用到队列。