题目：
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
想法：
二叉搜索树可以利用性质中序遍历先得到排序后的数组，然后双指针遍历记录最小差值。也可以直接中序遍历二叉搜索树，同样需要双指针，记录最小差值，这道题目需要注意一些细节问题，注意要在利用完pre指针后更新pre指针，还有result的初始化，要取最小差值，就用INT_MAX。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int result = INT_MAX;
TreeNode* pre = nullptr;
void traversal(TreeNode* cur) {
if (cur == nullptr) return ;
traversal(cur -> left);
if (pre != nullptr) {
result = min(result, cur -> val - pre -> val);
}
pre = cur;
traversal(cur -> right);
return ;
}
int getMinimumDifference(TreeNode* root) {
traversal(root);
return result;
}
};
题目：
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
想法：
这里用了两种解法，一种是不利用二叉搜索树的性质，用任何方式遍历一次二叉树，用哈希表记录元素的频率，然后用sort自定义比较规则，按频率排序，最后把频率排在前面的元素取出来，注意可能不止一个，注意代码中break的使用。另外这里学到了一点新知识，自定义比较规则函数因为在类内，要写成static，在类内部取类内部的函数地址有点麻烦。还有就是map的具体写法，我自己写成了类的成员变量，也可以在类的成员函数中传递引用，熟悉这个做法。
第二种方法是利用二叉搜索树性质，中序遍历就是有序的从小到大，注意处理当前节点时频率的记录和更新，为了判断当前节点值是否等于上一个节点值需要pre指针，如果频率追平最大频率，当前节点值要放入结果数组，如果超过最大频率，要及时清空结果数组，并放入当前节点值，还要记得及时更新pre指针。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
//如果不是二叉搜索树的做法
// class Solution {
// private:
// unordered_map<int, int> map;
// //递归遍历二叉树 用map统计元素出现频率 map key:元素 value:频率
// void searchTree(TreeNode* cur) {
// if (cur == nullptr) return ;
// if (cur -> left) searchTree(cur -> left);
// map[cur -> val]++;
// if (cur -> right) searchTree(cur -> right);
// return ;
// }
// //自定义比较规则 把元素按照频率从高到低排序
// //注意 自定义比较这个函数写在类里面 要static才行
// //自己写没加const 加不加都对
// bool static myComp(const pair<int, int>& p1, const pair<int, int>& p2) {
// return p1.second > p2.second;
// }
// public:
// vector<int> findMode(TreeNode* root) {
// searchTree(root);
// //注意这里的创建方式，一定要记下来
// vector<pair<int, int>> vec(map.begin(), map.end());
// sort(vec.begin(), vec.end(), Solution::myComp);
// vector<int> result;
// //这里犯了错误 自己写直接用下标访问，是错的
// result.push_back(vec[0].first);
// for (int i = 1; i < vec.size(); i++) {
// if (vec[i].second == vec[i - 1].second) {
// result.push_back(vec[i].first);
// } else {
// //这里break的用法也要记住
// break;
// }
// }
// return result;
// }
// };
//下面代码和自己写的区别在于没有写成员变量map，而是在递归函数中传递map的引用，也要熟悉这种写法
// class Solution {
// private:
// void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历
// if (cur == NULL) return ;
// map[cur->val]++; // 统计元素频率
// searchBST(cur->left, map);
// searchBST(cur->right, map);
// return ;
// }
// bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
// return a.second > b.second;
// }
// public:
// vector<int> findMode(TreeNode* root) {
// unordered_map<int, int> map; // key:元素，value:出现频率
// vector<int> result;
// if (root == NULL) return result;
// searchBST(root, map);
// vector<pair<int, int>> vec(map.begin(), map.end());
// sort(vec.begin(), vec.end(), cmp); // 给频率排个序
// result.push_back(vec[0].first);
// for (int i = 1; i < vec.size(); i++) {
// // 取最高的放到result数组中
// if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
// else break;
// }
// return result;
// }
// };
//利用二叉搜索树的性质 中序遍历是从小到大遍历
class Solution {
private:
//记录上一个节点
TreeNode* pre =nullptr;
//记录当前频率
int count = 0;
//记录最大频率
int maxCount = 0;
//记录众数的集合
vector<int> result;
//递归函数 不需要返回值
void searchBST(TreeNode* cur) {
//终止条件
if (cur == nullptr) return ;
searchBST(cur -> left);
//第一个节点
if (pre == nullptr) {
count = 1;
} else if (pre -> val == cur -> val) {
count++;
} else {
count = 1;
}
//这个先后顺序很重要
if (count == maxCount) {
result.push_back(cur -> val);
}
//判断是否更新最大频率
if (count > maxCount) {
maxCount = count;
result.clear();
result.push_back(cur -> val);
}
//自己写忘记更新pre了
pre = cur;
searchBST(cur -> right);
return ;
}
public:
vector<int> findMode(TreeNode* root) {
searchBST(root);
return result;
}
};
题目：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
想法：
这里只学了递归法，用后序遍历，这样可以做到自底向上的处理。（需要自己体会一下自底向上）处理逻辑就是如果遇到了目标的两个节点就直接返回该节点，如果当前节点左右子节点返回都是有效节点，那就直接返回当前节点就是最近的公共祖先。这个规则可以解决所有情况。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//递归法
//终止条件
if (root == nullptr) return nullptr;
if (root -> val == p ->val || root -> val == q -> val) return root;
//递归
TreeNode* leftResult = lowestCommonAncestor(root -> left, p, q);
TreeNode* rightResult = lowestCommonAncestor(root -> right, p, q);
if (leftResult && rightResult) {
return root;
} else if (leftResult == nullptr && rightResult != nullptr) {
return rightResult;
} else if (leftResult != nullptr && rightResult == nullptr) {
return leftResult;
} else {
return nullptr;
}
}
};