Java 数据结构与算法-树
树的基础知识
树是算法面试经常遇到的数据结构之一，在实际工作中也有可能经常用到……
应聘者在准备算法面试时最需要重视的是二叉树……
二叉树是一种典型的具有递归性质的数据结构。二叉树的根节点可能有子节点，子节点又是对应子树的根节点，它可能也有自己的子节点。这就类似于 “子又生孙，孙又生子，子子孙孙无穷尽也”。由于二叉树本身就是递归的数据结构，因此很多与二叉树相关的面试题用递归的代码解决就很直观
……
二叉树的深度优先搜索
与二叉树相关的面试题绝大部分都是为了考查二叉树的遍历。第 7 章介绍了二叉树的广度优先搜索，本节将深入探讨二叉树的深度优先搜索及典型的面试题。二叉树的深度优先搜索可以细分为中序遍历、前序遍历和后序遍历
中序遍历
……
第一，递归有其固有的局限性。如果二叉树的深度（从根节点到叶节点的最长路径的长度）太大，那么递归的代码可能会导致调用栈溢出的问题。第二，递归的代码实在过于简单，面试官也希望增加面试的难度，因此在面试的时候经常会限制编写递归的中序遍历的代码
把递归代码改写成迭代的代码通常需要用到栈，改写中序遍历的代码也不例外……
前序遍历
……
前序遍历的递归代码实现和中序遍历的递归代码实现类似……
前序遍历的迭代代码实现和中序遍历的迭代代码实现也很类似……
后序遍历
后序遍历的递归代码实现和中序遍历的递归代码实现类似……
和中序遍历、前序遍历相比，后序遍历的迭代代码要稍微复杂一点。当达到某个节点时，如果之前还没有遍历过它的右子树就得前往它的右子节点，如果之前已经遍历过它的右子树那么就可以遍历这个节点。也就是说，此时要根据它的右子树此前有没有遍历过来确定是否应该遍历当前的节点。如果此前右子树已经遍历过，那么在右子树中最后一个遍历的节点应该是右子树的根节点，也就是当前节点的右子节点。可以记录遍历的前一个节点。如果一个节点存在右子节点并且右子节点正好是前一个被遍历的节点，那么它的右子树已经遍历过，现在是时候遍历当前的节点了
3 种遍历方法小节
下面比较中序遍历、前序遍历和后序遍历这 3 种不同遍历算法的代码。它们的递归代码都很简单，只需要调整代码的顺序就能写出对应算法的代码
它们的迭代代码也很类似，如它们都需要用到一个栈，而且代码的基本结构很相像，都有两个 while 循环并且它们的条件都一样。需要留意遍历当前节点的时机。前序遍历一边顺着指向左子节点的指针移动一边遍历当前的节点，而中序遍历和后序遍历则顺着指向左子节点的指针移动时只将节点放入栈中，并不遍历遇到的节点。只有当到达最左子节点之后再从栈中取出节点遍历。后序遍历最复杂，还需要保存前一个遍历的节点，并根据前一个遍历的节点是否为当前节点的右子节点来决定此时是否可以遍历当前的节点
不管是哪种深度优先搜索算法，也不管是递归代码还是迭代代码，如果二叉树有 n 个节点，那么它们的时间复杂度都是 O(n)。如果二叉树的深度为 h，那么它们的空间复杂度都是 O(h)。在二叉树中，二叉树的深度 h 的最小值是 log2(n+1)，最大值为 n……
3 种不同的二叉树深度优先搜索算法都有递归和迭代两种代码实现。这 6 段我们一定要深刻理解并能熟练写出正确的代码。这是因为很多与二叉树相关的面试题实际上都是在考查二叉树的深度优先搜索，理解中序遍历、前序遍历和后序遍历算法并能熟练写出代码，这些面试题都能迎刃而解。请看下面几个例题
面试题 47：二叉树剪枝
题目：一棵二叉树的所有节点的值要么是 0 要么是 1，请剪除该二叉树中所有节点的值全都是 0 的子树
public static TreeNode pruneTree(TreeNode root) {
if (root == null) {
return null;
}
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
if (root.left == null && root.right == null && root.val == 0) {
return null;
}
return root;
}
上述代码实质上是实现了递归的后序遍历。每当遍历到一个节点，如果该节点符合条件，则将该节点删除。由于是后序遍历，因此先对根节点 root 的左右子树递归调用函数 pruneTree 删除左右子树中节点值全是 0 的子树。只有当 root 的左右子树全部为空，并且它自己的值也是 0 时，整个节点才能被删除……
面试题 48：序列化和反序列化二叉树
题目：请设计一个算法将二叉树序列化成一个字符串，并能将该字符串反序列化出原来二叉树的算法
……以前序遍历的顺序遍历二叉树最适合序列化。如果采用前序遍历的顺序，那么二叉树的根节点最先序列化到字符串中，然后是左子树，最后是右子树。这样做的好处是在反序列化时最方便，从字符串中读出的第 1 个数值一定是根节点的值
……尽管 null 节点通常没有在图上画出来，但它们对树的结构是至关重要的。因此，应该把 null 节点序列化成一个特殊的字符串。如果把 null 节点序列化成 “#”……
public static String serialize(TreeNode root) {
if (root == null) {
return "#";
}
String leftStr = serialize(root.left);
String rightStr = serialize(root.right);
return root.val + "," + leftStr + "," + rightStr;
}
public static TreeNode deserialize(String data) {
String[] nodeStrs = data.split(",");
int[] i = {0};
return dfs(nodeStrs, i);
}
private static TreeNode dfs(String[] strs, int[] i) {
String str = strs[i[0]];
i[0]++;
if (str.equals("#")) {
return null;
}
TreeNode node = new TreeNode(Integer.valueOf(str));
node.left = dfs(strs, i);
node.right = dfs(strs, i);
return node;
}
在上述代码中，字符串数组 nodeStrs 保存分隔之后的所有节点对应的字符串，可以根据数组中的每个字符串逐一构建二叉树的每个节点。递归函数 dfs 的每次执行都会从字符串数组中取出一个字符串并以此反序列化出一个节点（如果取出的字符串是 “#”，则返回 null 节点）
我们需要一个下标去扫描字符串数组 nodeStrs 中的每个字符串。通常用一个整数值来表示数组的下标，但在上述代码中却定义了一个长度为 1 的整数数组 i。这是因为递归函数 dfs 每反序列化一个节点时下标就会增加 1，并且函数的调用者需要知道下标增加了。如果函数 dfs 的第 2 个参数 i 是整数类型，那么即使在函数体内修改 i 的值，修改之后的值也不能传递给它的调用者。但把 i 定义为整数数组之后，可以修改整数数组中的数字，修改之后的数值就能传给它的调用者
面试题 49：从根节点到叶节点的路径数字之和
题目：在一棵二叉树中所有节点都在 0~9 的范围之内，从根节点到叶节点的路径表示一个数字。求二叉树中所有路径表示的数字之和
基于二叉树前序遍历的参考代码如下所示：
public static int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private static int dfs(TreeNode root, int path) {
if (root == null) {
return 0;
}
path = path * 10 + root.val;
if (root.left == null && root.right == null) {
return path;
}
return dfs(root.left, path) + dfs(root.right, path);
}
在这个题目中，路径的定义是从根节点开始到叶节点结束，因此上属代码中只有遇到叶节点才返回路径表示的数字（代码中的变量 path）。如果在遇到叶节点之前就结束路径，由于不符合题目要求，因此应该返回 0。这是辅助函数 dfs 的第 1 条 if 语句（root==null）为 true 时返回 0 的原因
面试题 50：向下的路径节点值之和
题目：给定一棵二叉树和一个值 sum，求二叉树中节点值之和等于 sum 的路径的数目。路径的定义为二叉树中顺着指向子节点的指针向下移动所经过的节点，但不一定从根节点开始，也不一定到叶节点结束
在这个题目中，二叉树的路径的定义发生了改变，它不一定从根节点开始，也不一定到叶节点结束。路径的起止节点的不确定性给计算路径经过的节点值之和带来了很大的难度
虽然路径不一定从根节点开始，但仍然可以求得从根节点开始到达当前遍历节点的路径所经过的节点值之和……
如果在路径上移动时把所有累加的节点值之和都保存下来，就容易知道是否存在从任意节点出发的值为给定 sum 的路径……
有了前面的经验，就可以采用二叉树深度优先搜索来解决与路径相关的问题。当遍历到一个节点时，先累加从根节点开始的路径上的节点值之和，再计算到它的左右子节点的路径的节点值之和。这就是典型的前序遍历的顺序
public static int pathSum(TreeNode root, int sum) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
return dfs(root, sum, map, 0);
}
private static int dfs(TreeNode root, int sum, Map<Integer, Integer> map, int path) {
if (root == null) {
return 0;
}
path += root.val;
int count = map.getOrDefault(path - sum, 0);
map.put(path, map.getOrDefault(path, 0) + 1);
count += dfs(root.left, sum, map, path);
count += dfs(root.right, sum, map, path);
map.put(path, map.get(path) - 1);
return count;
}
上述代码用参数 path 表示从根节点开始的路径已经累加的节点值之和，并保存到哈希表 map 中。哈希表的键是累加的节点值之和，哈希表的值是每个节点值之和出现的次数。当遍历到一个节点时，就把当前节点的值累加到参数 path。如果这个和之前出现过，则将出现的次数加 1；如果这个和之前没有出现过，那么这是它的第 1 次出现。然后更新哈希表 map 保存累加节点值之和 path 及出现的次数
辅助函数 dfs 实现了递归的前序遍历，该函数遍历到二叉树的一个节点时将递归地遍历它的子节点。因此，当该函数结束时，程序将回到节点的父节点，也就是说，在函数结束之前需要将当前节点从路径中删除，从根节点到当前节点累加的节点值之和也要从哈希表 map 中删除。这是在函数 dfs 返回之前更新哈希表 map 把参数 path 出现的次数减 1 的原因
面试题 51：节点值之和最大的路径
题目：在二叉树中将路径定义为顺着节点之间的连接从任意一个节点开始到达任意一个节点所经过的所有节点。路径中至少包含一个节点，不一定经过二叉树的根节点，也不一定经过叶节点。给定非空的一棵二叉树，请求出二叉树所有路径上节点值之和的最大值
这个题目中二叉树路径的定义又和前面的不同。这里的路径最主要的特点是路径有可能同时经过一个节点的左右子节点……
……需要先求出左右子树中路径节点值之和的最大值（左右子树中的路径不经过当前节点），再求出经过根节点的路径节点值之和的最大值，最后对三者进行比较得到最大值。由于需要先求出左右子树的路径节点值之和的最大值，再求根节点，这看起来就是后序遍历……
public static int maxPathSum(TreeNode root) {
int[] maxSum = {Integer.MIN_VALUE};
dfs(root, maxSum);
return maxSum[0];
}
private static int dfs(TreeNode root, int[] maxSum) {
if (root == null) {
return 0;
}
int[] maxSumLeft = {Integer.MIN_VALUE};
int left = Math.max(0, dfs(root.left, maxSumLeft));
int[] maxSumRight = {Integer.MIN_VALUE};
int right = Math.max(0, dfs(root.right, maxSumRight));
maxSum[0] = Math.max(maxSumLeft[0], maxSumRight[0]);
maxSum[0] = Math.max(maxSum[0], root.val + left + right);
return root.val + Math.max(left, right);
}
上述代码按照后序遍历的顺序遍历二叉树的每个节点。由于求左右子树的路径节点值之和的最大值与求整棵二叉树的路径节点值之和的最大值是同一个问题，因此用递归的代码解决这个问题最直观
代码中的参数 maxSum 是路径节点值之和的最大值。由于递归函数 dfs 需要把这个最大值传给它的调用者，因此参数 maxSum 被定义为长度为 1 的数组。先递归调用函数 dfs 求得左右子树的路径节点值之和的最大值 maxSumLeft 及 maxSumRight，再求出经过当前节点 root 的路径的节点值之和的最大值，那么参数 maxSum 就是这 3 个值的最大值
函数的返回值是经过当前节点 root 并前往其左子树或右子树的路径的节点值之和的最大值。它的父节点要根据这个返回值求路径的节点值之和。由于同时经过左右子树的路径不能经过父节点，因此返回值是变量 left 与 right 的较大值加上当前节点 root 的值
二叉搜索树
二叉搜索树是一类特殊的二叉树，它的左子节点总是小于或等于根节点，而右子节点总是大于或等于根节点……
二叉树的 3 种不同的深度优先搜索算法都适用于二叉搜索树，但中序遍历是解决二叉搜索树相关面试题最常用的思路，这是因为中序遍历按照节点值递增的顺序遍历二叉搜索树的每个节点……
普通的二叉树中根据节点值查找对应的节点需要遍历这棵二叉树，因此需要 O(n) 的时间。但如果是二叉搜索树就可以根据其特性进行优化……如果二叉搜索树的高度为 h，那么在二叉搜索树中根据节点值查找对应节点的时间复杂度是 O(h)
面试题 52：展平二叉搜索树
题目：给定一棵二叉搜索树，请调整节点的指针使每个节点都没有左子节点。调整之后的树看起来像一个链表，但仍然是二叉搜索树
看起来需要按照节点的值递增的顺序遍历二叉搜索树中的每个节点，并将节点用指向右子节点的指针连接起来。这就容易让人联想到二叉树的中序遍历，只是在这里每遍历到一个节点要把前一个节点的指向右子节点的指针指向它。基于中序遍历的参考代码如下所示：
public static TreeNode increasingBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode prev = null;
TreeNode first = null;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (prev != null) {
prev.right = cur;
} else {
first = cur;
}
prev = cur;
cur.left = null;
cur = cur.right;
}
return first;
}
上述代码只是对二叉树中序遍历的迭代代码稍作修改。变量 prev 表示前一个遍历到的节点。在遍历到当前节点 cur 时，把变量 prev 的右子节点的指针指向 cur，并将 cur 指向左子节点的指针设为 null
展平之后的二叉搜索树的根节点是值最小的节点，因此也是中序遍历第 1 个被遍历到的节点。在上述代码中，变量 first 就是第 1 个被遍历到的节点，在展平之后就是二叉搜索树的根节点，因此将它作为函数的返回值
面试题 53：二叉搜索树的下一个节点
题目：给定一棵二叉搜索树和它的一个节点 p，请找出按中序遍历的顺序该节点 p 的下一个节点。假设二叉搜索树中节点的值都是唯一的
时间复杂度 O(n) 的解法
解决这个问题的最直观的思路就是采用二叉树的中序遍历……由于中序遍历会逐一遍历二叉树的每个节点，如果二叉树有 n 个节点，那么这种思路的时间复杂度就是 O(n)……栈的空间复杂度为 O(h)，其中 h 为二叉树的深度
时间复杂度 O(h) 的解法
下面换一个角度来看待二叉搜索树中节点 p 的中序遍历下一个节点。首先下一个节点的值一定不会小于节点 p 的值，而且还是大于或等于节点 p 的值的所有节点中值最小的一个……
public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode cur = root;
TreeNode result = null;
while (cur != null) {
if (cur.val > p.val) {
result = cur;
cur = cur.left;
} else {
cur = cur.right;
}
}
return result;
}
如果把二叉树的深度记为 h，那么该算法的时间复杂度为 O(h)。同时，上述代码除几个变量外没有其他内存开销，因此空间复杂度是 O(1)
面试题 54：所有大于或等于节点的值之和
题目：给定一棵二叉搜索树，请将它的每个节点的值替换成树中大于或等于该节点值的所有节点值之和。假设二叉树中节点的值唯一
首先需要注意到这个题目与节点值的大小顺序相关，因为要找出比某节点的值大的所有节点。在二叉搜索树的常用遍历算法中，只有中序遍历是按照节点值递增的顺序遍历所有节点的……
如果能够按照节点值从大到小的顺序遍历二叉搜索树……通常的中序遍历是先遍历左子树，再遍历根节点，最后遍历右子树……那么只需要改变中序遍历的顺序，先遍历右子树，再遍历根节点，最后遍历左子树，这样遍历的顺序就颠倒过来了
基于这种颠倒的中序遍历，可以编写出如下所示的代码：
public static TreeNode convertBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
int sum = 0;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.right;
}
cur = stack.pop();
sum += cur.val;
cur.val = sum;
cur = cur.left;
}
return root;
}
面试题 55：二叉搜索树迭代器
题目：请实现二叉搜索树迭代器 BSTIterator，它主要有如下 3 个函数
- 构造函数：输入二叉树的根节点初始化该迭代器
- 函数 next：返回二叉搜索树中下一个最小的节点的值
- 函数 hasNext：返回二叉搜索树是否还有下一个节点
基于中序遍历的迭代代码实现二叉搜索树的迭代器的参考代码如下所示：
class BSTIterator {
TreeNode cur;
Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
cur = root;
stack = new Stack<>();
}
public boolean hasNext() {
return cur != null || !stack.isEmpty();
}
public int next() {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
int val = cur.val;
cur = cur.right;
return val;
}
}
在上述代码中，栈 stack 的大小为 O(h)。由于这个栈一直存在，因此函数 hasNext 和 next 的空间复杂度是 O(h)。函数 hasNext 的时间复杂度显然是 O(1)。如果二叉搜索树有 n 个节点，调用 n 次函数 next 才能遍历完所有的节点，因此函数 next 的平均时间复杂度是 O(1)
面试题 56：二叉搜索树中两个节点的值之和
题目：给定一棵二叉搜索树和一个值 k，请判断该二叉搜索树中是否存在值之和等于 k 的两个节点。假设二叉搜索树中节点的值均唯一
利用哈希表，空间复杂度为 O(n) 的解法
public static boolean findTarget1(TreeNode root, int k) {
Set<Integer> set = new HashSet<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (set.contains(k - cur.val)) {
return true;
}
set.add(cur.val);
cur = cur.right;
}
return false;
}
上述算法其实适合任何二叉树，并没有利用二叉搜索树的特性。接下来根据二叉搜索树的特性做进一步的优化
应用双指针，空间复杂度为 O(h) 的解法
面试题 6 介绍了如何利用双指针判断在排序数组中是否包含两个和为 k 的数字，即把第 1 个指针指向数组的第 1 个（也是最小的）数字，把第 2 个指针指向数组的最后一个（也是最大的）数字。如果两个数字之和等于 k，那么就找到了两个符合要求的数字；如果两个数字之和大于 k，那么向左移动第 2 个指针使它指向更小的数字；如果两个数字之和小于 k，那么向右移动第 1 个指针使它指向更大的数字……
class BSTIteratorReversed {
TreeNode cur;
Stack<TreeNode> stack;
public BSTIteratorReversed(TreeNode root) {
cur = root;
stack = new Stack<>();
}
public boolean hasPrev() {
return cur != null || !stack.isEmpty();
}
public int prev() {
while (cur != null) {
stack.push(cur);
cur = cur.right;
}
cur = stack.pop();
int val = cur.val;
cur = cur.left;
return val;
}
}
有了 BSTIteratorReversed 的迭代器，每次调用函数 prev 都将按照从大到小的顺序从二叉搜索树中取出一个节点的值……可以很容易地运用双指针的思路，其参考代码如下所示：
public static boolean findTarget2(TreeNode root, int k) {
if (root == null) {
return false;
}
BSTIterator iterNext = new BSTIterator(root);
BSTIteratorReversed iterPrev = new BSTIteratorReversed(root);
int next = iterNext.next();
int prev = iterPrev.prev();
while (next != prev) {
if (next + prev == k) {
return true;
}
if (next + prev < k) {
next = iterNext.next();
} else {
prev = iterPrev.prev();
}
}
return false;
}
……如果它们的和小于 k，就用 BSTIterator 取出一个更大的节点值；如果它们的和大于 k，就用 BSTIteratorReversed 取出一个更小的节点值
这两个迭代器一起使用可能需要遍历整棵二叉搜索树，因此时间复杂度是 O(n)。每个迭代器都需要一个大小为 O(h) 的栈，因此总的空间复杂度是 O(h)。在大多数情况下，二叉树的深度远小于二叉树的节点数，因此第二种算法的总体空间效率要优于第 1 种算法
TreeSet 和 TreeMap 的应用
二叉搜索树是一种很有用的数据结构。如果二叉搜索树有 n 个节点，深度为 h，那么查找、添加和删除操作的时间复杂度都是 O(h)。如果二叉搜索树是平衡的，那么深度 h 近似等于 logn。但在极端情况下（如每个节点只有一个子节点），树的深度 h 等于 n-1，此时二叉搜索树的查找、添加和删除操作的时间复杂度都退化成 O(n)。二叉搜索树是否平衡对二叉搜索树的时间效率至关重要
实现一棵平衡的二叉搜索树对于面试来说并不是一件容易的事情。Java 根据红黑树这种平衡的二叉搜索树实现 TreeSet 和 TreeMap 两种数据结构，如果应聘者在面试的时候需要使用平衡的二叉树来高效地解决问题，则可以直接引用
TreeSet 实现了接口 Set，它内部的平衡二叉树中每个节点只包含一个值，根据这个值的查找、添加和删除操作的时间复杂度都是 O(logn)。除 Set 定义的接口之外，TreeSet 的常用函数如下表所示：
| 序号 | 函数 | 函数功能 |
|---|---|---|
| 1 | ceiling | 返回键大于或等于给定值的最小键；如果没有则返回 null |
| 2 | floor | 返回键小于或等于给定值的最大键；如果没有则返回 null |
| 3 | higher | 返回键大于给定值的最小键；如果没有则返回 null |
| 4 | lower | 返回键小于给定值的最大键；如果没有则返回 null |
TreeMap 实现了接口 Map。和 TreeSet 不一样，TreeMap 内部的平衡二叉搜索树中的每个节点都是一个包含键值和值的映射。可以根据键值实现时间复杂度为 O(logn) 的查找、添加和删除操作。除 Map 定义的接口之外，TreeMap 的常用函数如下表所示：
| 序号 | 函数 | 函数功能 |
|---|---|---|
| 1 | ceilingEntry/ceilingKey | 返回键值大于或等于给定值的最小映射/键；如果没有则返回 null |
| 2 | floorEntry/floorKey | 返回键值小于或等于给定值的最大映射/键；如果没有则返回 null |
| 3 | higherEntry/higherKey | 返回键大于给定值的最小映射/键；如果没有则返回 null |
| 4 | lowerEntry/lowerKey | 返回键小于给定值的最大映射/键；如果没有则返回 null |
如果面试题的数据集合是动态的（即题目要求逐步在数据集合中添加更多的数据），并且需要根据数据的大小实现快速查找，那么可能需要用到 TreeSet 或 TreeMap
第 5 章介绍了哈希表（HashSet 或 HashMap）中查找、添加和删除操作的时间复杂度都是 O(1)，是非常高效的。但它有一个缺点，哈希表只能根据键进行查找，只能判断该键是否存在。如果需要根据数值的大小查找，如查找数据集合中比某个值大的所有数字中的最小的一个，哈希表就无能为力
如果在一个排序的动态数组（如 Java 的 ArrayList）中根据数值的大小进行查找，则可以应用二分查找算法实现时间效率为 O(logn) 的查找。但排序的动态数组的添加和删除操作的时间复杂度是 O(n)
由于 TreeSet 或 TreeMap 能够保证其内部的二叉搜索树是平衡的，因此它们的查找、添加和删除操作的时间复杂度都是 O(logn)，综合来看它们比动态排序数组更加高效
面试题 57：值和下表之差都在给定的范围内
题目：给定一个整数数组 nums 和两个正数 k、t，请判断是否存在两个不同的下标 i 和 j 满足 i 和 j 之差的绝对值不大于给定的 k，并且两个数值 nums[i] 和 nums[j] 的差的绝对值不大于给定的 t
例如，如果输入数组 {1, 2, 3, 1}，k 为 3，t 为 0，由于下标 0 和下标 3 对应的数字之差的绝对值为 0，因此返回 true。如果输入数组 {1, 5, 9, 1, 5, 9}，k 为 2，t 为 3，由于不存在两个下标之差小于或等于 2 且它们差的绝对值小于或等于 3 的数字，因此此时应该返回 false
首先考虑最直观的解法。可以逐一扫描数组中的每个数字。对于每个数字 nums[i]，需要逐一检查它前面的 k 个数字是否存在从 nums[i]-t 到 nums[i]+t 的范围内的数字。如果存在，则返回 true。这种思路很容易用两个嵌套的循环实现
由于数组中的每个数字都要和 k 个数字进行比较，如果数组的长度为 n，那么这种解法的时间复杂度是 O(nk)
时间复杂度为 O(nlogk) 的解法
接下来尝试优化时间复杂度。逐一扫描数组中的每个数字。对于每个数字 nums[i]，应该先从它前面的 k 个数字中找出小于或等于 nums[i] 的最大的数字，如果这个数字与 nums[i] 的差的绝对值不大于 t，那么就找到了一组符合条件的两个数字。否则，再从它前面的 k 个数字中找出大于或等于 nums[i] 的最小的数字，如果这个数字与 nums[i] 的差的绝对值不大于 t，就找到了一组符合条件的两个数字
需要从一个大小为 k 的内容变化的数据容器中找出小于或等于某个数字的最大值及大于或等于某个数字的最小值，这正是 TreeSet 或 TreeMap 适用的场景。因为这个容器只需要保存数字，所以可以用 TreeSet 来保存每个数字 nums[i] 前面的 k 个数字。基于 TreeSet 的参考代码如下所示：
public static boolean containsNearbyAlmostDuplicate1(int[] nums, int k, int t) {
TreeSet<Long> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
Long lower = set.floor((long) nums[i]);
if (lower != null && lower >= (long) nums[i] - t) {
return true;
}
Long upper = set.ceiling((long) nums[i]);
if (upper != null && upper <= (long) nums[i] + t) {
return true;
}
set.add((long) nums[i]);
if (i >= k) {
set.remove((long) nums[i - k]);
}
}
return false;
}
在上述代码中，变量 set 是一个 TreeSet，它的大小为 k，因此空间复杂度是 O(k)。对它做查找、添加和删除操作的时间复杂度都是 O(logk)，因此对于一个长度为 n 的数组而言，它的时间复杂度是 O(nlogk)
时间复杂度为 O(n) 的解法
下面换一种思路来解决这个问题。由于这个题目关心的是差的绝对值小于或等于 t 的数字，因此可以将数字放入若干大小为 t+1 的桶中。例如，将从 0 到 t 的数字放入编号为 0 的桶中，从 t+1 到 2t+1 的数字放入编号为 1 的桶中。其他数字以此类推。这样做的好处是如果两个数字被放入同一个桶中，那么它们的差的绝对值一定小于或等于 t
还是逐一扫描数组中的数字。如果当前扫描到数字 num，那么它将放入编号为 id 的桶中。如果这个桶中之前已经有数字，那么就找到两个差的绝对值小于或等于 t 的数字。如果桶中之前没有数字，则再判断编号为 id-1 和 id+1 的这两个相邻桶中是否存在与 num 的差的绝对值小于或等于 t 的数字。因为其他桶中的数字与 num 的差的绝对值一定大于 t，所以不需要判断其他的桶中是否有符合条件的数字
基于这种思路编写的代码如下所示：
public static boolean containsNearByAlmostDuplicate2(int[] nums, int k, int t) {
Map<Integer, Integer> buckets = new HashMap<>();
int bucketSize = t + 1;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int id = getBucketId(num, bucketSize);
if (buckets.containsKey(id)
|| (buckets.containsKey(id - 1) && buckets.get(id - 1) + t >= num)
|| (buckets.containsKey(id + 1) && buckets.get(id + 1) - t <= num)) {
return true;
}
buckets.put(id, num);
if (i >= k) {
buckets.remove(getBucketId(nums[i - k], bucketSize));
}
}
return false;
}
private static int getBucketId(int num, int bucketSize) {
return num >= 0 ? num / bucketSize : (num + 1) / bucketSize - 1;
}
在上述代码中，随着下标的移动，总是有最多 k 个桶来存储数组 nums 的值，每个桶中只有一个数字（当需要往同一个桶中装入两个数字时，意味着数字的差的绝对值小于或等于 t，意味着方法结束，返回 true）
哈希表 buckets 的大小是 k，因此，空间复杂度是 O(k)。哈希表中的查找、添加和删除操作的时间复杂度都是 O(1)，因此，对于一个长度为 n 的数组而言，它的时间复杂度是 O(n)
面试题 58：日程表
题目：请实现一个类型 MyCalendar 用来记录自己的日程安排，该类型用方法 book(int start, int end) 在日程表中添加一个时间区域为 [start, end) 的事项（这是一个半开半闭区间）。如果 [start, end) 中之前没有安排其他事项，则成功添加该事项并返回 true；否则，不能添加该事项，并返回 false
如果待添加的事项占用的时间区间是 [m, n)，就需要找出开始时间小于 m 的所有事项中开始最晚的一个，以及开始时间大于 m 的所有事项中开始最早的一个。如果待添加的事项和这两个事项都没有重叠，那么该事项可以添加在日程表中（之前的事项都是这样添加的，因此各不重叠）
基于 TreeMap 的参考代码如下所示：
class MyCalendar {
private TreeMap<Integer, Integer> events;
public MyCalendar() {
events = new TreeMap<>();
}
public boolean book(int start, int end) {
Map.Entry<Integer, Integer> event = events.floorEntry(start);
if (event != null && event.getValue() > start) {
return false;
}
event = events.ceilingEntry(start);
if (event != null && event.getKey() < end) {
return false;
}
events.put(start, end);
return true;
}
}
本章小结
本章介绍了树这种数据结构，尤其着重介绍了二叉树。与二叉树相关的面试题大多与遍历相关，本章通过大量的面试题全面介绍了二叉树的中序遍历、前序遍历和后序遍历这 3 种深度优先搜索算法。笔者强烈建议读者对这 3 种遍历的循环和迭代代码烂熟于心，这样在解决与二叉树相关的面试题时才能得心应手
二叉搜索树是一种特殊的二叉树，在二叉搜索树中进行搜索、添加和删除操作的平均时间复杂度都是 O(logn)。如果按照中序遍历的顺序遍历一棵二叉搜索树，那么按照从小到大的顺序依次遍历每个节点。由于这个特性，与二叉搜索树相关的很多面试题都适合使用中序遍历解决
Java 中提供的 TreeSet 和 TreeMap 这两种数据结构实现了平衡二叉搜索树。如果需要动态地在一个排序的数据集合中添加元素，或者需要根据数据的大小查找，那么可以使用 TreeSet 或 TreeMap 解决