前言

代码随想录算法训练营day21

一、Leetcode 530.二叉搜索树的最小绝对差

1.题目

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3] 输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49] 输出：1

提示：

1. 树中节点的数目范围是 [2, 104]
2. 0 <= Node.val <= 105

注意：本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/minimum-absolute-difference-in-bst

2.解题思路

方法一：中序遍历

思路与算法

考虑对升序数组 aa 求任意两个元素之差的绝对值的最小值，答案一定为相邻两个元素之差的最小值，即

ans=min⁡i=0n−2{a[i+1]−a[i]}ans=i=0minn−2{a[i+1]−a[i]}

其中 nn 为数组 aa 的长度。其他任意间隔距离大于等于 22 的下标对 (i,j)(i,j) 的元素之差一定大于下标对 (i,i+1)(i,i+1) 的元素之差，故不需要再被考虑。

回到本题，本题要求二叉搜索树任意两节点差的绝对值的最小值，而我们知道二叉搜索树有个性质为二叉搜索树中序遍历得到的值序列是递增有序的，因此我们只要得到中序遍历后的值序列即能用上文提及的方法来解决。

朴素的方法是经过一次中序遍历将值保存在一个数组中再进行遍历求解，我们也可以在中序遍历的过程中用 prepre 变量保存前驱节点的值，这样即能边遍历边更新答案，不再需要显式创建数组来保存，需要注意的是 prepre 的初始值需要设置成任意负数标记开头，下文代码中设置为 −1−1。

二叉树的中序遍历有多种方式，包括递归、栈、Morris 遍历等，读者可选择自己最擅长的来实现。下文代码提供最普遍的递归方法来实现，其他遍历方法的介绍可以详细看「94. 二叉树的中序遍历的官方题解」，这里不再赘述。

3.代码实现

```java class Solution { public: void dfs(TreeNode* root, int& pre, int& ans) { if (root == nullptr) { return; } dfs(root->left, pre, ans); if (pre == -1) { pre = root->val; } else { ans = min(ans, root->val - pre); pre = root->val; } dfs(root->right, pre, ans); } int getMinimumDifference(TreeNode* root) { int ans = INT_MAX, pre = -1; dfs(root, pre, ans); return ans; } };
```

二、Leetcode 501.二叉搜索树中的众数

1.题目

给你一个含重复值的二叉搜索树(BST)的根节点 root ，找出并返回 BST 中的所有 众数(即，出现频率最高的元素)。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

1. 结点左子树中所含节点的值 小于等于 当前节点的值
2. 结点右子树中所含节点的值 大于等于 当前节点的值
3. 左子树和右子树都是二叉搜索树

示例 1：

输入：root = [1,null,2,2] 输出：[2]

示例 2：

输入：root = [0] 输出：[0]

提示：

1. 树中节点的数目在范围 [1, 104] 内
2. -105 <= Node.val <= 105

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree

2.解题思路

方法一：中序遍历

思路与算法

首先我们一定能想到一个最朴素的做法：因为这棵树的中序遍历是一个有序的序列，所以我们可以先获得这棵树的中序遍历，然后从扫描这个中序遍历序列，然后用一个哈希表来统计每个数字出现的个数，这样就可以找到出现次数最多的数字。但是这样做的空间复杂度显然不是 O(1)O(1) 的，原因是哈希表和保存中序遍历序列的空间代价都是 O(n)O(n)。

首先，我们考虑在寻找出现次数最多的数时，不使用哈希表。 这个优化是基于二叉搜索树中序遍历的性质：一棵二叉搜索树的中序遍历序列是一个非递减的有序序列。例如：

1. 1
2. /   \

0 2 / \ / -1 0 2

这样一颗二叉搜索树的中序遍历序列是 {−1,0,0,1,2,2}{−1,0,0,1,2,2}。我们可以发现重复出现的数字一定是一个连续出现的，例如这里的 00 和 22，它们都重复出现了，并且所有的 00 都集中在一个连续的段内，所有的 22 也集中在一个连续的段内。我们可以顺序扫描中序遍历序列，用 basebase 记录当前的数字，用 countcount 记录当前数字重复的次数，用 maxCountmaxCount 来维护已经扫描过的数当中出现最多的那个数字的出现次数，用 answeranswer 数组记录出现的众数。每次扫描到一个新的元素：

1. 首先更新 basebase 和 countcount:
2.     如果该元素和 basebase 相等，那么 countcount 自增 11；
3.     否则将 basebase 更新为当前数字，countcount 复位为 11。
4. 然后更新 maxCountmaxCount：
5.     如果 count=maxCountcount=maxCount，那么说明当前的这个数字(basebase)出现的次数等于当前众数出现的次数，将 basebase 加入 answeranswer 数组；
6.     如果 count>maxCountcount>maxCount，那么说明当前的这个数字(basebase)出现的次数大于当前众数出现的次数，因此，我们需要将 maxCountmaxCount 更新为 countcount，清空 answeranswer 数组后将 basebase 加入 answeranswer 数组。

我们可以把这个过程写成一个 updateupdate 函数。这样我们在寻找出现次数最多的数字的时候就可以省去一个哈希表带来的空间消耗。

然后，我们考虑不存储这个中序遍历序列。 如果我们在递归进行中序遍历的过程中，访问当了某个点的时候直接使用上面的 updateupdate 函数，就可以省去中序遍历序列的空间，代码如下。

3.代码实现

```java class Solution { List answer = new ArrayList (); int base, count, maxCount;

1. public int[] findMode(TreeNode root) {
2.     dfs(root);
3.     int[] mode = new int[answer.size()];
4. for (int i = 0; i < answer.size(); ++i) {
5. mode[i] = answer.get(i);
6.     }
7. return mode;
8. }
9. 
10. public void dfs(TreeNode o) {
11. if (o == null) {
12. return;
13.     }
14.     dfs(o.left);
15.     update(o.val);
16.     dfs(o.right);
17. }
18. 
19. public void update(int x) {
20. if (x == base) {
21. ++count;
22.     } else {
23. count = 1;
24.         base = x;
25.     }
26. if (count == maxCount) {
27.         answer.add(base);
28.     }
29. if (count > maxCount) {
30.         maxCount = count;
31.         answer.clear();
32.         answer.add(base);
33.     }
34. }

}

```

三、Leetcode 236. 二叉树的最近公共祖先

1.题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

示例 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 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2 输出：1

提示：

1. 树中节点数目在范围 [2, 105] 内。
2. -109 <= Node.val <= 109
3. 所有 Node.val 互不相同 。
4. p != q
5. p 和 q 均存在于给定的二叉树中。

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree

2.解题思路

方法一：递归

我们递归遍历整棵二叉树，定义 fxfx 表示 xx 节点的子树中是否包含 pp 节点或 qq 节点，如果包含为 true，否则为 false。那么符合条件的最近公共祖先 xx 一定满足如下条件：

(flson && frson) ∣∣ ((x = p ∣∣ x = q) && (flson ∣∣ frson))(flson && frson) ∣∣ ((x = p ∣∣ x = q) && (flson ∣∣ frson))

其中 lsonlson 和 rsonrson 分别代表 xx 节点的左孩子和右孩子。初看可能会感觉条件判断有点复杂，我们来一条条看，flson && frsonflson && frson 说明左子树和右子树均包含 pp 节点或 qq 节点，如果左子树包含的是 pp 节点，那么右子树只能包含 qq 节点，反之亦然，因为 pp 节点和 qq 节点都是不同且唯一的节点，因此如果满足这个判断条件即可说明 xx 就是我们要找的最近公共祖先。再来看第二条判断条件，这个判断条件即是考虑了 xx 恰好是 pp 节点或 qq 节点且它的左子树或右子树有一个包含了另一个节点的情况，因此如果满足这个判断条件亦可说明 xx 就是我们要找的最近公共祖先。

你可能会疑惑这样找出来的公共祖先深度是否是最大的。其实是最大的，因为我们是自底向上从叶子节点开始更新的，所以在所有满足条件的公共祖先中一定是深度最大的祖先先被访问到，且由于 fxfx 本身的定义很巧妙，在找到最近公共祖先 xx 以后，fxfx 按定义被设置为 true ，即假定了这个子树中只有一个 pp 节点或 qq 节点，因此其他公共祖先不会再被判断为符合条件。

下图展示了一个示例，搜索树中两个节点 9 和 11 的最近公共祖先。

3.代码实现

```java class Solution {

1. private TreeNode ans;
2. 
3. public Solution() {
4.     this.ans = null;
5. }
6. 
7. private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
8. if (root == null) return false;
9. boolean lson = dfs(root.left, p, q);
10. boolean rson = dfs(root.right, p, q);
11. if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
12.         ans = root;
13.     } 
14. return lson || rson || (root.val == p.val || root.val == q.val);
15. }
16. 
17. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
18.     this.dfs(root, p, q);
19. return this.ans;
20. }

}

```