一、二叉搜索树的最小绝对差
1.题目
Leetcode：第 530 题
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1
示例 2：
输入：root = [1,0,48,null,null,12,49] 输出：1
2.解题思路
1.一般递归法：使用递归法遍历整个二叉树，得出保存所有节点元素的数组，再遍历数组找出最小差值。
2.双指针递归法：通过栈来进行二叉树的遍历，模拟了二叉树的中序遍历。在遍历过程中，始终保持一个指向前一个访问节点的指针 pre，并在每次访问新节点时更新最小差值 result。由于栈的特性，可以保证在每次从栈中弹出节点时，都已经访问过它的所有左子树节点，因此我们可以计算当前节点与前一个节点的差值。这样，可以在一次遍历中找到所有节点值之间的最小差值。
3.迭代法：使用迭代法遍历整个二叉树，找出不同节点值之间的最小差值 。
3.实现代码
// 一、实现计算二叉树最小差值的算法（一般递归法）。
class Solution1 {
public:
vector<int> vec; // 定义一个vec，用于存储二叉树节点的值，
// 定义一个名为traversal的私有成员函数，用于执行二叉树的中序遍历。
// 参数root是当前遍历到的二叉树节点指针。
void traversal(TreeNode* root) {
if (root == NULL) return; // 如果当前节点为空，直接返回，不执行任何操作。
traversal(root->left); // 递归调用traversal函数遍历当前节点的左子树。
vec.push_back(root->val); // 访问当前节点，将其值添加到vec中。
traversal(root->right); // 递归调用traversal函数遍历当前节点的右子树。
}
// 定义一个名为getMinimumDifference的公共成员函数，用于计算给定二叉树中所有节点值之间的最小差值。
// 参数root是二叉树的根节点指针。
int getMinimumDifference(TreeNode* root) {
vec.clear(); // 清空vec，为新的中序遍历做准备。
traversal(root); // 调用traversal函数，传入根节点，执行中序遍历，并将结果存储在vec中。
if (vec.size() < 2) return 0; // 检查vec中的元素数量，如果小于2，则不存在有效的差值，返回0。
int result = INT_MAX;// 初始化最小差值result为INT_MAX，表示最大的整数值。
for (int i = 1; i < vec.size(); i++) {// 遍历vec中的元素，计算并更新最小差值。
result = min(result, vec[i] - vec[i - 1]); // 计算当前元素与前一个元素的差值，并与已知的最小差值result进行比较。
}
return result; // 返回计算得到的最小差值。
}
};
// 二、实现计算二叉树最小差值的算法（双指针递归法）。
class Solution2 {
public:
int result = INT_MAX; // 初始化结果变量result为整数的最大值INT_MAX，表示开始时最小差值为无穷大。
TreeNode* pre = NULL; // 定义一个指向TreeNode的指针pre，用于记录遍历过程中前一个访问的节点。
// 定义一个名为traversal的私有成员函数，用于执行二叉树的遍历。
// 参数cur是当前遍历到的二叉树节点指针。
void traversal(TreeNode* cur) {
if (cur == NULL) return; // 如果当前节点为空，直接返回，不执行任何操作。
traversal(cur->left); // 递归调用traversal函数遍历当前节点的左子树。
if (pre != NULL) { // 如果pre不为空，说明我们已经遍历过至少一个节点，可以计算差值。
result = min(result, cur->val - pre->val);// 更新结果变量result为当前节点值与前一个节点值之差的最小值。
}
pre = cur; // 更新pre为当前节点，因为在下一次递归调用中，当前节点将成为新的前一个节点。
traversal(cur->right); // 递归调用traversal函数遍历当前节点的右子树。
}
// 定义一个名为getMinimumDifference的公共成员函数，用于启动遍历过程并返回最小差值。
// 参数root是二叉树的根节点指针。
int getMinimumDifference(TreeNode* root) {
traversal(root);// 调用traversal函数，传入根节点，开始遍历二叉树。
return result; // 返回结果result，即二叉树中所有节点值之间的最小差值。
}
};
// 三、实现计算二叉树最小差值的算法（迭代法）。
class Solution3 {
public:
// 定义一个名为getMinimumDifference的公共成员函数，用于计算给定二叉树中所有节点值之间的最小差值。
// 参数root是二叉树的根节点指针。
int getMinimumDifference(TreeNode* root) {
stack<TreeNode*> st; // 定义一个栈st，用于存放二叉树的节点指针，辅助进行迭代遍历。
TreeNode* cur = root; // 定义一个当前节点指针cur，初始指向根节点。
TreeNode* pre = NULL; // 定义一个前一个节点指针pre，初始为NULL，用于记录遍历过程中的前一个节点值。
int result = INT_MAX; // 初始化结果result为整数的最大值INT_MAX，表示开始时最小差值为无穷大。
while (cur != NULL || !st.empty()) { // 当当前节点不为空，或者栈st不为空时，继续遍历。
if (cur != NULL) { // 如果当前节点不为空，执行以下操作：
st.push(cur); // 将当前节点压入栈st。
cur = cur->left; // 将cur更新为当前节点的左子节点，准备遍历左子树。
}
else { // 如果当前节点为空，执行以下操作：
cur = st.top(); // 将栈顶节点作为当前节点。
st.pop(); // 弹出栈顶节点。
// 如果pre不为空，说明我们之前已经访问过至少一个节点，可以计算差值。
if (pre != NULL) {
result = min(result, cur->val - pre->val); // 更新结果result为当前节点值与前一个节点值之差的最小值。
}
pre = cur; // 更新pre为当前节点，因为在下一次迭代中，当前节点将成为新的前一个节点。
cur = cur->right; // 将cur更新为当前节点的右子节点，准备遍历右子树。
}
}
return result; // 返回结果result，即二叉树中所有节点值之间的最小差值。
}
};
二、二叉搜索树中的众数
1.题目
Leetcode：第 501 题
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2] 输出：[2]
示例 2：
输入：root = [0] 输出：[0]
2.解题思路
通过中序遍历二叉搜索树，并在遍历过程中跟踪连续出现相同元素的次数。如果遇到不同的元素，或者遍历结束，则将当前的连续元素数量与最大连续元素数量进行比较。如果相等，就将该元素的值添加到结果向量中。最终，findMode 函数返回包含出现次数最多元素的数组。
3.实现代码
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// 定义一个结构体TreeNode，用于表示二叉树的节点。
struct TreeNode {
int val; // 存储节点的值。
TreeNode* left; // 指向该节点左子树的指针。
TreeNode* right; // 指向该节点右子树的指针。
// TreeNode的构造函数，用于创建一个TreeNode实例。
// 参数x是节点的值，left和right默认为NULL，表示没有左右子节点。
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 一、查找二叉搜索树中的众数（递归法）。
class Solution1 {
public:
int maxCount = 0; // 定义一个整数maxCount，用于存储遍历过程中遇到的最长连续元素的数量。
int count = 0;// 定义一个整数count，用于存储当前连续出现的元素数量。
TreeNode* pre = NULL; // 定义一个指向TreeNode的指针pre，用于记录遍历过程中前一个访问的节点。
vector<int> result; // 定义一个容器result，用于存储出现次数最多的元素。
// 定义一个名为searchBST的私有成员函数，用于递归遍历二叉搜索树。
// 参数cur是当前遍历到的二叉树节点指针。
void searchBST(TreeNode* cur) {
if (cur == NULL) return; // 如果当前节点为空，直接返回。
searchBST(cur->left); // 递归遍历当前节点的左子树。
// 如果pre为空（即这是遍历的起始节点），或者当前节点的值与pre相同（即连续出现），则增加count。
if (pre == NULL) {
count = 1;
}
else if (pre->val == cur->val) {
count++;
}
else {
count = 1; // 否则，重置count为1。
}
pre = cur; // 更新pre为当前节点。
// 如果当前的连续元素数量count等于最大连续元素数量maxCount，则将当前节点的值添加到结果result中。
if (count == maxCount) {
result.push_back(cur->val);
}
if (count > maxCount) { // 如果计数大于最大值频率
maxCount = count; // 更新最大频率
result.clear(); // 清空result，之前result里的元素都失效了
result.push_back(cur->val);
}
searchBST(cur->right); // 递归遍历当前节点的右子树。
return; // 这里返回是为了结束函数调用，实际上在递归中不需要显式返回。
}
// 定义一个名为findMode的公共成员函数，用于启动搜索过程并返回出现次数最多的元素列表。
// 参数root是二叉树的根节点指针。
vector<int> findMode(TreeNode* root) {
count = 0; // 重置当前连续元素数量。
maxCount = 0; // 重置最大连续元素数量。
pre = NULL; // 重置前一个访问的节点指针。
result.clear(); // 清空结果，为新的搜索做准备。
searchBST(root); // 调用searchBST函数，传入根节点，开始递归遍历。
return result;// 返回结果result，包含出现次数最多的元素。
}
};
// 二、查找二叉搜索树中的众数（迭代法）。
class Solution2 {
public:
// 定义一个名为findMode的公共成员函数，用于启动搜索过程并返回出现次数最多的元素列表。
// 参数root是二叉树的根节点指针。
vector<int> findMode(TreeNode* root) {
stack<TreeNode*> st; // 定义一个栈st，用于存放二叉树的节点指针，辅助进行迭代遍历。
TreeNode* cur = root; // 定义一个当前节点指针cur，初始指向根节点。
TreeNode* pre = NULL; // 定义一个前一个节点指针pre，初始为NULL，用于记录遍历过程中的前一个节点值。
int maxCount = 0; // 初始化最大连续元素数量maxCount为0。
int count = 0; // 初始化当前连续元素数量count为0。
vector<int> result; // 定义一个容器result，用于存储出现次数最多的元素。
// 当当前节点不为空，或者栈st不为空时，继续遍历。
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur); // 如果当前节点不为空，将当前节点压入栈st。
cur = cur->left; // 将cur更新为当前节点的左子节点，准备遍历左子树。
}
else {
cur = st.top(); // 如果当前节点为空，将栈顶节点作为当前节点。
st.pop(); // 弹出栈顶节点。
// 如果pre为空（即这是遍历的起始节点），则重置count为1。
if (pre == NULL) {
count = 1;
}
// 如果当前节点的值与pre相同（即连续出现），则增加count。
else if (pre->val == cur->val) {
count++;
}
else {
count = 1; // 否则，重置count为1。
}
pre = cur; // 更新pre为当前节点。
// 如果当前的连续元素数量count等于最大连续元素数量maxCount，则将当前节点的值添加到结果result中。
if (count == maxCount) {
result.push_back(cur->val);
}
// 如果当前的连续元素数量count大于最大连续元素数量maxCount，则更新maxCount并清空result，将当前节点的值添加到result中。
if (count > maxCount) {
maxCount = count;
result.clear();
result.push_back(cur->val);
}
cur = cur->right; // 将cur更新为当前节点的右子节点，准备遍历右子树。
}
}
return result; // 返回结果result，包含出现次数最多的元素。
}
};
三、二叉树的最近公共祖先
1.题目
Leetcode：第 236 题
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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
2.解题思路
使用递归法遍历二叉树，找到p和q节点，并求出最近公共祖先。
3.实现代码
#include <iostream>
#include <vector>
using namespace std;
// 定义一个结构体TreeNode，用于表示二叉树的节点。
struct TreeNode {
int val; // 存储节点的值。
TreeNode* left; // 指向该节点左子树的指针。
TreeNode* right; // 指向该节点右子树的指针。
// TreeNode的构造函数，用于创建一个TreeNode实例。
// 参数x是节点的值，left和right默认为NULL，表示没有左右子节点。
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 寻找二叉树的最近公共祖先（递归法）
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 如果当前节点root是节点q或p之一，或者root为空，则返回当前节点root作为可能的最近公共祖先。
if (root == q || root == p || root == NULL) return root;
// 递归调用lowestCommonAncestor函数在当前节点root的左子树中查找p和q的最近公共祖先，并将结果存储在left。
TreeNode* left = lowestCommonAncestor(root->left, p, q);
// 递归调用lowestCommonAncestor函数在当前节点root的右子树中查找p和q的最近公共祖先，并将结果存储在right。
TreeNode* right = lowestCommonAncestor(root->right, p, q);
// 如果在左右子树中都找到了p和q的最近公共祖先（即left和right都不为空），则当前节点root是p和q的最近公共祖先。
if (left != NULL && right != NULL) return root;
// 如果只在右子树中找到了p和q的最近公共祖先（即left为空，right不为空），则返回right。
if (left == NULL && right != NULL) return right;
// 如果只在左子树中找到了p和q的最近公共祖先（即left不为空，right为空），则返回left。
else if (left != NULL && right == NULL) return left;
// 如果在左右子树中都没有找到p和q的最近公共祖先（即left和right都为空），或者p和q都位于当前节点的同一侧（左或右），则返回NULL。
else {
return NULL;
}
}
};
ps：以上皆是本人在探索算法旅途中的浅薄见解，诚挚地希望得到各位的宝贵意见与悉心指导，若有不足或谬误之处，还请多多指教。