LeetCode530.二叉搜索树的最小绝对差值
题目描述：
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1
示例 2：
输入：root = [1,0,48,null,null,12,49] 输出：1
思路：
·求最小绝对差值，因为二叉搜索树是一个有序的树，所以，可以使用中序遍历，再去求保存到数组中的元素的最小绝对差值，这样就会简单很多了
·使用快慢指针（双指针）进行遍历，也可以进行求解，将快指针定义在第一位，慢指针定义为NULL，每次共同移动一个结点
使用数组遍历二叉树代码如下：
class Solution {
public:
vector<int> vec;
void traversal(TreeNode* cur){//使用中序遍历二叉树，将二叉树保存至数组中
if(cur == NULL) return ;
traversal(cur->left);
vec.push_back(cur->val);
traversal(cur->right);
}
int getMinimumDifference(TreeNode* root) {
int result = INT_MAX;
traversal(root);
for(int i = 1;i < vec.size();i++){//求最小绝对差值
result = min(result,vec[i]-vec[i-1]);
}
return result;
}
};双指针法：
class Solution {
public:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur){
if(cur == NULL) return ;
traversal(cur->left);
if(pre != NULL){
result = min(result,cur->val - pre->val);
}
pre = cur;
traversal(cur->right);
}
int getMinimumDifference(TreeNode* root) {
traversal(root);
return result;
}
};总结：遇到二叉搜索树的题目时，如果有要求最值、差值之类的，都要思考一下二叉搜索树是有序的，要利用好这一隐藏条件。
同时要学会在递归中如何记录前后两个指针，这是一个小技巧，我们前面也有用过，后面的题目也一定会用。
LeetCode.501二叉搜索树中的众数
题目描述：
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2] 输出：[2]
示例 2：
输入：root = [0] 输出：[0]
解题思路：
·注意题目中需要遍历的是二叉搜索树，而不是普通二叉树，如果是普通二叉树会难很多，所以这里就不做过多赘述，而二叉搜索树是有序的这一特点要记牢。
·与前一题一样，使用双指针进行解题，定义cur为快指针，pre为慢指针，若cur->val==pre->val则count++，再定义maxCount，若maxCount==count则放入数组中，若不等于则清空数组，最终返回数组
代码如下：
class Solution {
private:
int count = 0;
int maxCount = 0;
TreeNode* pre = NULL;
vector<int> vec;
void traversal(TreeNode* cur){
if(cur == NULL) return ;
traversal(cur->left);
if(pre == NULL){
count = 1;
}else if(pre->val == cur->val){
count++;
}else{
count = 1;
}
pre = cur;
if(maxCount == count){
vec.push_back(cur->val);
}
if(maxCount < count){
maxCount = count;
vec.clear();
vec.push_back(cur->val);
}
traversal(cur->right);
}
public:
vector<int> findMode(TreeNode* root) {
count = 0;
pre = NULL;
traversal(root);
return vec;
}
};总结：本题意在加深对二叉搜索树的理解，当然了，作者我在没看题解之前也是没有想到解法的，要多做题，脑中的想法才会多
LeetCode236.二叉树的最近公共祖先
题目描述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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
解题思路：
·这道题的解题思路，需要自底向上查找，就能找到公共祖先了，所以解这道题使用的是后续遍历，根据左右子树的返回值，来处理中节点的逻辑
代码如下：
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == q || root == p || root == NULL) return root;
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
if(left != NULL && right != NULL) return root;
if(left == NULL && right != NULL) return right;
else if(left != NULL && right == NULL) return left;
else return NULL;
}
};总结：
1.求最下公共祖先，需要自底向上遍历，所以要使用后序遍历，也就是回溯
2.在回溯的过程中，必然要遍历整棵二叉树，即使已经找到了结果，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就算left和right）做逻辑判断
3.要理解如果返回值left为空，right不为空，为什么要返回right，为什么可以用返回right传给上一层结果
需要对二叉树，递归和回溯有一定的理解，有些难度。
