- 剑指Offer（专项突破版）：树
- 面试题47：二叉树剪枝
- 面试题48：序列化和反序列化二叉树
- 面试题49：从根节点到叶节点的路径数字之和
- 面试题50：向下的路径节点值之和
- 面试题51：节点值之和最大的路径
- 面试题52：展平二叉搜索树
- 面试题53：二叉搜索树的下一个节点
- 面试题54：所有大于或等于节点的值之和
- 面试题55：二叉搜索树迭代器
- 面试题56：二叉搜索树中两个节点的值之和
- 面试题57：值和下标之差都在给定的范围内
- 面试题58：日程表
- 划线笔记
题目：一棵二叉树的所有节点的值要么是0要么是1，请剪除该二叉树中所有节点的值全都是0的子树。例如，在剪除图8.21（a）中二叉树中所有节点值都为0的子树之后的结果如图8.2（b）所示。
面试题48：序列化和反序列化二叉树题目：请设计一个算法将二叉树序列化成一个字符串，并能将该字符串反序列化出原来二叉树的算法。
面试题49：从根节点到叶节点的路径数字之和题目：在一棵二叉树中所有节点都在0～9的范围之内，从根节点到叶节点的路径表示一个数字。求二叉树中所有路径表示的数字之和。例如，图8.4的二叉树有3条从根节点到叶节点的路径，它们分别表示数字395、391和302，这3个数字之和是1088。
面试题50：向下的路径节点值之和题目：给定一棵二叉树和一个值sum，求二叉树中节点值之和等于sum的路径的数目。路径的定义为二叉树中顺着指向子节点的指针向下移动所经过的节点，但不一定从根节点开始，也不一定到叶节点结束。例如，在如图8.5所示中的二叉树中有两条路径的节点值之和等于8，其中，第1条路径从节点5开始经过节点2到达节点1，第2条路径从节点2开始到节点6。
面试题51：节点值之和最大的路径题目：在二叉树中将路径定义为顺着节点之间的连接从任意一个节点开始到达任意一个节点所经过的所有节点。路径中至少包含一个节点，不一定经过二叉树的根节点，也不一定经过叶节点。给定非空的一棵二叉树，请求出二叉树所有路径上节点值之和的最大值。例如，在如图8.6所示的二叉树中，从节点15开始经过节点20到达节点7的路径的节点值之和为42，是节点值之和最大的路径。
面试题52：展平二叉搜索树题目：给定一棵二叉搜索树，请调整节点的指针使每个节点都没有左子节点。调整之后的树看起来像一个链表，但仍然是二叉搜索树。例如，把图8.82（a）中的二叉搜索树按照这个规则展平之后的结果如图8.8（b）所示。
面试题53：二叉搜索树的下一个节点题目：给定一棵二叉搜索树和它的一个节点p，请找出按中序遍历的顺序该节点p的下一个节点。假设二叉搜索树中节点的值都是唯一的。例如，在图8.9的二叉搜索树中，节点8的下一个节点是节点9，节点11的下一个节点是null。
面试题54：所有大于或等于节点的值之和题目：给定一棵二叉搜索树，请将它的每个节点的值替换成树中大于或等于该节点值的所有节点值之和。假设二叉搜索树中节点的值唯一。例如，输入如图8.10（a）所示的二叉搜索树，由于有两个节点的值大于或等于6（即节点6和节点7），因此值为6节点的值替换成13，其他节点的值的替换过程与此类似，所有节点的值替换之后的结果如图8.10（b）所示。
面试题55：二叉搜索树迭代器题目：请实现二叉搜索树的迭代器BSTIterator，它主要有如下3个函数。
● 构造函数：输入二叉搜索树的根节点初始化该迭代器。
● 函数next：返回二叉搜索树中下一个最小的节点的值。
● 函数hasNext：返回二叉搜索树是否还有下一个节点。
面试题56：二叉搜索树中两个节点的值之和题目：给定一棵二叉搜索树和一个值k，请判断该二叉搜索树中是否存在值之和等于k的两个节点。假设二叉搜索树中节点的值均唯一。例如，在如图8.123所示的二叉搜索树中，存在值之和等于12的两个节点（节点5和节点7），但不存在值之和为22的两个节点。
面试题57：值和下标之差都在给定的范围内题目：给定一个整数数组nums和两个正数k、t，请判断是否存在两个不同的下标i和j满足i和j之差的绝对值不大于给定的k，并且两个数值nums[i]和nums[j]的差的绝对值不大于给定的t。
面试题58：日程表题目：请实现一个类型MyCalendar用来记录自己的日程安排，该类型用方法book（int start，int end）在日程表中添加一个时间区域为[start，end）的事项（这是一个半开半闭区间）。如果[start，end）中之前没有安排其他事项，则成功添加该事项并返回true；否则，不能添加该事项，并返回false。
划线笔记树是算法面试经常遇到的数据结构之一，在实际工作中也有可能经常用到。
在二叉树中每个节点最多只有两个子节点，可以分别把它们称为左子节点和右子节点。
由于二叉树本身就是递归的数据结构，因此很多与二叉树相关的面试题用递归的代码解决就很直观。
与二叉树相关的面试题绝大部分都是为了考查二叉树的遍历。
二叉树的深度优先搜索又可以细分为中序遍历、前序遍历和后序遍历。
如果按照中序遍历的顺序，则先遍历二叉树的左子树，然后遍历二叉树的根节点，最后遍历二叉树的右子树。
如果输入的二叉树的根节点不为空，则先遍历它的左子树，然后遍历根节点，最后遍历右子树。
递归有其固有的局限性。如果二叉树的深度（从根节点到叶节点的最长路径的长度）太大，那么递归的代码可能会导致调用栈溢出的问题。
把递归代码改写成迭代的代码通常需要用到栈
二叉树的遍历总是从根节点开始的，但当第 1 次到达根节点时，并不是马上遍历根节点，而是顺着指向左子节点的指针向下直到叶节点，也就是找到第 1 个真正被遍历的节点。
为了在一个节点被遍历之后能够接着回去遍历它的父节点，可以在顺着指向左子节点的指针遍历二叉树时把遇到的每个节点都添加到一个栈中。当一个节点被遍历了之后，就可以从栈中得到它的父节点。
变量 cur 表示当前遍历的节点。如果该节点有左子节点，按照中序遍历的顺序，应该先遍历它的左子树。于是顺着指向左子节点的指针一直向下移动，并将沿途遇到的每个节点都添加到栈 stack 之中。第 2 个 while 循环结束之后，最左子节点（顺着指向左子节点的指针到达的最远的节点）位于栈顶，将它从栈顶出栈并遍历。按照中序遍历的顺序，在遍历一个节点之后再遍历它的右子树，因此把变量 cur 指向它的右子节点，开始下一轮的遍历，直到所有节点都遍历完为止。
前序遍历的递归代码实现和中序遍历的递归代码实现类似，只需要调整递归函数中代码的顺序就可以。
二叉树后序遍历的递归代码和其他两种遍历方法的递归代码类似，只需要调整递归函数 dfs 中代码的顺序，把遍历根节点的代码移到最后就可以。
和中序遍历、前序遍历相比，后序遍历的迭代代码要稍微复杂一点。
当达到某个节点时，如果之前还没有遍历过它的右子树就得前往它的右子节点，如果之前已经遍历过它的右子树那么就可以遍历这个节点。
可以记录遍历的前一个节点。如果一个节点存在右子节点并且右子节点正好是前一个被遍历的节点，那么它的右子树已经遍历过，现在是时候遍历当前的节点了。
下一个遍历的节点一定是它的父节点，而父节点之前已经存放到栈中，所以需要将变量 cur 重置为 null，这样下一次就可以将它的父节点出栈并遍历。
它们的递归代码都很简单，只需要调整代码的顺序就能写出对应算法的代码。
它们的迭代代码也很类似，如它们都需要用到一个栈，而且代码的基本结构很相像，都有两个 while 循环并且它们的条件都一样。
前序遍历一边顺着指向左子节点的指针移动一边遍历当前的节点，而中序遍历和后序遍历则顺着指向左子节点的指针移动时只将节点放入栈中，并不遍历遇到的节点。只有当到达最左子节点之后再从栈中取出节点遍历。后序遍历最复杂，还需要保存前一个遍历的节点，并根据前一个遍历的节点是否为当前节点的右子节点来决定此时是否可以遍历当前的节点。
不管是哪种深度优先搜索算法，也不管是递归代码还是迭代代码，如果二叉树有_n_个节点，那么它们的时间复杂都是_O_（n）。
如果二叉树的深度为_h_，那么它们的空间复杂度都是_O_（h）。
3 种不同的二叉树深度优先搜索算法都有递归和迭代两种代码实现。这 6 段代码我们一定要深刻理解并能熟练写出正确的代码。这是因为很多与二叉树相关的面试题实际上都是在考查二叉树的深度优先搜索，理解中序遍历、前序遍历和后序遍历算法并能熟练写出代码，这些面试题都能迎刃而解。
如果用后序遍历的顺序遍历到某个节点，那么它的左右子树的节点一定已经遍历过了。
每遍历到一个节点，就要确定它是否有左右子树，如果左右子树都是空的，并且节点的值是 0，那么也就可以删除这个节点。
所谓删除一个节点，就是返回 null 给它的父节点，这样这个节点就从这棵二叉树中消失。
只把节点的值序列化到字符串中是不够的。首先，要用一个分隔符（如逗号）把不同的节点分隔开。其次，还要考虑如何才能在反序列化的时候构建不同结构的二叉树。
尽管 null 节点通常没有在图上画出来，但它们对树的结构是至关重要的。因此，应该把 null 节点序列化成一个特殊的字符串。如果把 null 节点序列化成 “＃”
如果节点是 null 则返回特殊字符串 “＃”；否则生成一个字符串，它的开头是节点的值，然后是左子树序列化的结果，最后是右子树序列化的结果，因此这是按照前序遍历的顺序递归地序列化整棵二叉树。
由于把二叉树序列化成一个以逗号作为分隔符的字符串，因此可以根据分隔符把字符串分隔成若干子字符串，每个子字符串对应二叉树的一个节点。如果一个节点为 null，那么它和 “＃” 对应；否则这个节点将和一个表示它的值的子字符串对应。
可以调用递归函数解决反序列化子树的问题
字符串数组 nodeStrs 保存分隔之后的所有节点对应的字符串，可以根据数组中的每个字符串逐一构建二叉树的每个节点。递归函数 dfs 的每次执行都会从字符串数组中取出一个字符串并以此反序列化出一个节点（如果取出的字符串是 “＃”，则返回 null 节点）。
通常用一个整数值来表示数组的下标，但在上述代码中却定义了一个长度为 1 的整数数组 i。这是因为递归函数 dfs 每反序列化一个节点时下标就会增加 1，并且函数的调用者需要知道下标增加了。如果函数 dfs 的第 2 个参数 i 是整数类型，那么即使在函数体内修改 i 的值，修改之后的值也不能传递给它的调用者。但把 i 定义为整数数组之后，可以修改整数数组中的数字，修改之后的数值就能传给它的调用者。
首先考虑如何计算路径表示的数字。顺着指向子节点的指针路径向下遍历二叉树，每到达一个节点，相当于在路径表示的数字末尾添加一位数字。
每当遍历到一个节点时都计算从根节点到当前节点的路径表示的数字。如果这个节点还有子节点，就把这个值传下去继续遍历它的子节点。先计算到当前节点为止的路径表示的数字，再计算到它的子节点的路径表示的数字，这实质上就是典型的二叉树前序遍历。
如果在遇到叶节点之前就结束的路径，由于不符合题目要求，因此应该返回 0。
路径的定义是从根节点开始到叶节点结束，因此上述代码中只有遇到叶节点才返回路径表示的数字
与二叉树中路径相关的面试题有很多，通常这些面试题都可以用深度优先搜索解决，很少采用广度优先搜索。
虽然路径不一定从根节点开始，但仍然可以求得从根节点开始到达当前遍历节点的路径所经过的节点值之和。
如果在路径上移动时把所有累加的节点值之和都保存下来，就容易知道是否存在从任意节点出发的值为给定 sum 的路径。
当遍历到一个节点时，先累加从根节点开始的路径上的节点值之和，再计算到它的左右子节点的路径的节点值之和。这就是典型的前序遍历的顺序。
哈希表的键是累加的节点值之和，哈希表的值是每个节点值之和出现的次数。当遍历到一个节点时，就把当前的节点值累加到参数 path。如果这个和之前出现过，则将出现的次数加 1；如果这个和之前没有出现过，那么这是它第 1 次出现。然后更新哈希表 map 保存累加节点值之和 path 及出现的次数。
该函数遍历到二叉树的一个节点时将递归地遍历它的子节点。因此，当该函数结束时，程序将回到节点的父节点，也就是说，在函数结束之前需要将当前节点从路径中删除，从根节点到当前节点累加的节点值之和也要从哈希表 map 中删除。
路径的定义为二叉树中顺着指向子节点的指针向下移动所经过的节点，但不一定从根节点开始，也不一定到叶节点结束。
路径定义为顺着节点之间的连接从任意一个节点开始到达任意一个节点所经过的所有节点。路径中至少包含一个节点，不一定经过二叉树的根节点，也不一定经过叶节点。
求左右子树的路径节点值之和的最大值与求整棵二叉树的路径节点值之和的最大值是同一个问题
函数的返回值是经过当前节点 root 并前往其左子树或右子树的路径的节点值之和的最大值。它的父节点要根据这个返回值求路径的节点值之和。
二叉搜索树是一类特殊的二叉树，它的左子节点总是小于或等于根节点，而右子节点总是大于或等于根节点。
中序遍历是解决二叉搜索树相关面试题最常用的思路，这是因为中序遍历按照节点值递增的顺序遍历二叉搜索树的每个节点
如果二叉搜索树的高度为_h_，那么在二叉搜索树中根据节点值查找对应节点的时间复杂度是_O_（h）。
每遍历到一个节点要把前一个节点的指向右子节点的指针指向它。
首先下一个节点的值一定不会小于节点_p_的值，而且还是大于或等于节点_p_的值的所有节点中值最小的一个。
从根节点开始，每到达一个节点就比较根节点的值和节点_p_的值。如果当前节点的值小于或等于节点_p_的值，那么节点_p_的下一个节点应该在它的右子树。如果当前节点的值大于节点_p_的值，那么当前节点有可能是它的下一个节点。
此时当前节点的值比节点_p_的值大，但节点_p_的下一个节点是所有比它大的节点中值最小的一个，因此接下来前往当前节点的左子树，确定是否能找到值更小但仍然大于节点_p_的值的节点。重复这样的比较，直至找到最后一个大于节点_p_的值的节点，就是节点_p_的下一个节点。
由于 while 循环每运行一次都会顺着指向左子节点或右子节点的指针前往下一层节点，因此 while 循环执行的次数等于二叉搜索树的深度。如果把二叉树的深度记为_h_，那么该算法的时间复杂度为_O_（h）。
可以先遍历一遍二叉树求出所有节点的值之和 total，再用 total 减去 sum 即可。
通常的中序遍历是先遍历左子树，再遍历根节点，最后遍历右子树，由于左子树节点的值较小，右子树节点的值较大，因此总体上就是按照节点的值从小到大遍历的。如果要按照节点的值从大到小遍历，那么只需要改变中序遍历的顺序，先遍历右子树，再遍历根节点，最后遍历左子树，这样遍历的顺序就颠倒过来了。
如果允许修改输入的二叉搜索树，则可以在初始化迭代器时将它展平成除叶节点之外其他节点只有一个右子节点。这时二叉搜索树看起来像一个链表。然后用一个指针 P 指向展平后的二叉搜索树的根节点，如果指针 P 指向的节点不为 null，那么函数 hasNext 将返回 true。每次函数 next 被调用时都返回指针 P 指向节点的值，并将指针 P 朝着指向右子节点的指针向前移动一次。
如果不允许修改输入的二叉搜索树，那么可以在迭代器初始化时另外创建一个链表保存二叉树所有节点的值。
如果对二叉树的中序遍历的迭代代码足够熟悉，我们就会注意到中序遍历的迭代代码中有一个 while 循环，循环的条件为 true 时循环体每执行一次就遍历二叉树的一个节点。当 while 循环的条件为 false 时，二叉树中的所有节点都已遍历完。因此，中序遍历的迭代代码中的 while 循环可以看成迭代器 hasNext 的判断条件，而 while 循环体内执行的操作就是函数 next 执行的操作。
每遍历到一个节点（节点的值记为_v_），就在哈希表中查看是否存在值为_k-v_的节点。如果存在，就表示存在值之和等于_k_的两个节点。
实际上，在某种程度上可以把二叉搜索树看成一个排序的数组，因为按照中序遍历的顺序遍历二叉搜索树将得到一个递增的序列。
二叉搜索树是一种很有用的数据结构。如果二叉搜索树有_n_个节点，深度为_h_，那么查找、添加和删除操作的时间复杂度都是_O_（h）。如果二叉搜索树是平衡的，那么深度_h_近似等于 log_n_。但在极端情况下（如每个节点只有一个子节点），树的深度_h_等于_n_-1，此时二叉搜索树的查找、添加和删除操作的时间复杂度都退化成_O_（n）。
实现一棵平衡的二叉搜索树对于面试来说不是一件容易的事情。Java 根据红黑树这种平衡的二叉搜索树实现 TreeSet 和 TreeMap 两种数据结构，如果应聘者在面试的时候需要使用平衡的二叉树来高效地解决问题，则可以直接引用。
TreeSet 实现了接口 Set，它内部的平衡二叉树中的每个节点只包含一个值，根据这个值的查找、添加和删除操作的时间复杂度都是_O_（log_n_）。
TreeMap 实现了接口 Map。和 TreeSet 不一样，TreeMap 内部的平衡二叉搜索树中的每个节点都是一个包含键值和值的映射。可以根据键值实现时间复杂度为_O_（log_n_）的查找、添加和删除操作。
哈希表只能根据键进行查找，只能判断该键是否存在。
如果面试题的数据集合是动态的（即题目要求逐步在数据集合中添加更多的数据），并且需要根据数据的大小实现快速查找，那么可能需要用到 TreeSet 或 TreeMap。
如果在一个排序的动态数组（如 Java 的 ArrayList）中根据数值的大小进行查找，则可以应用二分查找算法实现时间效率为_O_（log_n_）的查找。但排序的动态数组的添加和删除操作的时间复杂度是_O_（n）。
由于 TreeSet 或 TreeMap 能够保证其内部的二叉搜索树是平衡的，因此它们的查找、添加和删除操作的时间复杂度都是_O_（log_n_），综合来看它们比动态排序数组更加高效。
可以逐一扫描数组中的每个数字。对于每个数字 nums[i]，需要逐一检查在它前面的_k_个数字是否存在从 nums[i]_-t_到 nums[i]+_t_的范围内的数字。如果存在，则返回 true。
逐一扫描数组中的每个数字。对于每个数字 nums[i]，应该先从它前面的_k_个数字中找出小于或等于 nums[i] 的最大的数字，如果这个数字与 nums[i] 的差的绝对值不大于_t_，那么就找到了一组符合条件的两个数字。否则，再从它前面的_k_个数字中找出大于或等于 nums[i] 的最小的数字，如果这个数字与 nums[i] 的差的绝对值不大于_t_，就找到了一组符合条件的两个数字
从一个大小为_k_的数据容器中找出小于或等于某个数字的最大值及大于或等于某个数字的最小值，这正是 TreeSet 或 TreeMap 适用的场景。
将数字放入若干大小为_t_+1 的桶中。例如，将从 0 到_t_的数字放入编号为 0 的桶中，从_t_+1 到 2_t_+1 的数字放入编号为 1 的桶中。其他数字以此类推。这样做的好处是如果两个数字被放入同一个桶中，那么它们的差的绝对值一定小于或等于_t_。
如果当前扫描到数字 num，那么它将放入编号为 id 的桶中。如果这个桶中之前已经有数字，那么就找到两个差的绝对值小于或等于_t_的数字。如果桶中之前没有数字，则再判断编号为 id-1 和 id-2 的这两个相邻的桶中是否存在与 num 的差的绝对值小于或等于_t_的数字。
由于这个题目的每个桶中只能装一个数字，因此 buckets 的值是装在桶中的一个数字。函数 getBucketID 用来确定每个数字应该放入的桶的编号。
buckets 是一个 HashMap，用来表示大小为_t_+1 的用来装数字的桶，它的键表示桶的编号。
如果待添加的事项占用的时间区间是 [m，n），就需要找出开始时间小于_m_的所有事项中开始最晚的一个，以及开始时间大于_m_的所有事项中开始最早的一个。
如果待添加的事项和这两个事项都没有重叠，那么该事项可以添加在日程表中。
如果用一个排序的动态数组（在 Java 中为 ArrayList）来保存日程表中的时间区间，那么查找的时间复杂度是_O_（log_n_），但排序数组中插入新的时间区间的时间复杂度是_O_（n）。
如果把时间区间存储到搜索二叉树中，那么在二叉搜索树中进行查找、插入和删除操作的时间复杂度都是_O_（log_n_）。
只是面试的时间通常是有限的，不一定来得及从头实现平衡的二叉搜索树的查找、添加等操作。幸运的是，Java 提供了 TreeMap 和 TreeSet 这两种二叉搜索树的数据结构，可以选择合适的类型来解决问题。
在 TreeMap 中，每个节点是一个映射，可以把时间区间的开始时间作为映射的键，把结束时间作为映射的值。
TreeMap 能够保证其背后的二叉搜索树是平衡的，如果二叉搜索树中有_n_个节点，即日程表中有_n_个时间区间，那么其查找函数 floorEntry 和 ceilingEntry 及添加函数 put 的时间复杂度都是_O_（log_n_），因此函数 book 的总体时间复杂度也是_O_（log_n_）
本章介绍了树这种数据结构，尤其着重介绍了二叉树。与二叉树相关的面试题大多与遍历相关，本章通过大量的面试题全面介绍了二叉树的中序遍历、前序遍历和后序遍历这 3 种深度优先搜索算法。笔者强烈建议读者对这 3 种遍历的循环和递归代码烂熟于心，这样在解决与二叉树相关的面试题时才能得心应手。
二叉搜索树是一种特殊的二叉树，在二叉搜索树中进行搜索、添加和删除操作的平均时间复杂度都是_O_（log_n_）。如果按照中序遍历的顺序遍历一棵二叉搜索树，那么按照从小到大的顺序依次遍历每个节点。由于这个特性，与二叉搜索树相关的很多面试题都适合使用中序遍历解决。
Java 中提供的 TreeSet 和 TreeMap 这两种数据结构实现了平衡二叉搜索树。如果需要动态地在一个排序的数据集合中添加元素，或者需要根据数据的大小查找，那么可以使用 TreeSet 或 TreeMap 解决。
说明：（a）一棵节点值要么是0要么是1的二叉树；（b）剪除所有节点值都为0的子树的结果 ↩︎
说明：（a）一棵有6个节点的二叉树；（b）展平成看起来是链表的二叉搜索树，每个节点都没有左子节点 ↩︎
说明：在该二叉搜索树中，存在值之和等于12的两个节点（节点5和节点7），但不存在值之和为22的两个节点 ↩︎
