算法训练营打卡Day18
目录
- 二叉搜索树的最小绝对差
- 二叉搜索树中的众数
- 二叉树的最近公共祖先
- 额外练手题目
题目1、二叉搜索树的最小绝对差
力扣题目链接(opens new window)
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
思路
遇到在二叉搜索树上求什么最值或者差值之类的问题，我们可以尝试把它想成在一个有序数组上求解。本题使用可以递归的方法，把二叉搜索树转换成有序数组，然后遍历一遍数组，从而求解最小绝对值差。
代码实现
python
class Solution:def __init__(self):self.vec = []def traversal(self, root):if root is None:returnself.traversal(root.left) #左self.vec.append(root.val) #中 将二叉搜索树转换为有序数组self.traversal(root.right) #右def getMinimumDifference(self, root):self.vec = [] #清空数组self.traversal(root)if len(self.vec) < 2: #遇到节点数少于2的二叉树return 0result = float('inf')for i in range(1, len(self.vec)):# 统计有序数组的最小差值result = min(result, self.vec[i] - self.vec[i - 1])return resultC++
class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {if (root == NULL) return;traversal(root->left);vec.push_back(root->val); // 将二叉搜索树转换为有序数组traversal(root->right);
}
public:int getMinimumDifference(TreeNode* root) {vec.clear();traversal(root);if (vec.size() < 2) return 0;int result = INT_MAX;for (int i = 1; i < vec.size(); i++) { // 统计有序数组的最小差值result = min(result, vec[i] - vec[i-1]);}return result;}
};另附超快运行解法（来自leetcode）
class Solution {
TreeNode* pre = nullptr;
int res = INT_MAX;
public:int getMinimumDifference(TreeNode* root) {if(root == nullptr) return 0;getMinimumDifference(root->left);if(pre == nullptr) pre = root;else {res = min(res, root->val - pre->val); pre = root;}getMinimumDifference(root->right);return res;}
};题目2、二叉搜索树中的众数
力扣题目链接(opens new window)
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],
返回[2].
思路
因为本题给定的二叉树是二叉搜索树，所以二叉树的中序遍历就是有序的，遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了。我们创建一个指针指向前一个节点，这样每次当前节点才能和前一个节点作比较。而且初始化的时候前一个节点为NULL，这样当前一个节点为NULL时候，我们就知道这是比较的第一个元素。
如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中，频率大于最大频率的时候，不仅要更新最大频率，而且要清空结果集，因为结果集之前的元素都失效了。
代码实现
C++
class Solution {
private:int maxCount = 0; // 最大频率int count = 0; // 统计频率TreeNode* pre = NULL;vector<int> result;void searchBST(TreeNode* cur) {if (cur == NULL) return ;searchBST(cur->left); // 左// 中if (pre == NULL) { // 第一个节点count = 1;} else if (pre->val == cur->val) { // 与前一个节点数值相同count++;} else { // 与前一个节点数值不同count = 1;}pre = cur; // 更新上一个节点if (count == maxCount) { // 如果和最大值相同，放进result中result.push_back(cur->val);}if (count > maxCount) { // 如果计数大于最大值频率maxCount = count; // 更新最大频率result.clear(); // 很关键的一步，不要忘记清空result，之前result里的元素都失效了result.push_back(cur->val);}searchBST(cur->right); // 右return ;}public:vector<int> findMode(TreeNode* root) {count = 0;maxCount = 0;pre = NULL; // 记录前一个节点result.clear();searchBST(root);return result;}
};题目3、 二叉树的最近公共祖先
力扣题目链接(opens new window)
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 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。因为根据定义最近公共祖先节点可以为节点本身。
思路
要想找到公共祖先，我们如果能自下而上地查找节点就好了，于是我们自然地想到回溯的思路，二叉树回溯的过程就是从下到上的。后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。接下来我们还需要判断一个节点是节点q和节点p的公共祖先，在处理递归的逻辑上有很多细节，包括是否要处理返回值以及如何处理返回值，是否要搜索整棵二叉树等。
代码实现
C++
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 { // (left == NULL && right == NULL)return NULL;}}
};可以参考更优的题解（来自leetcode），这里不作注解
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == p || root == q || root == nullptr) {return root;}TreeNode* l = lowestCommonAncestor(root->left, p, q);TreeNode* r = lowestCommonAncestor(root->right, p, q);if (l != nullptr and r != nullptr) {return root;}if (l != nullptr) {return l;}return r;}
};9月29日力扣每日一题
思路
对于在第k个人前的前k-1个人，如果这前k-1个人中有需要票数比第k个人的需要票数少的人，直接往count += tickets[i],否则加上第k个人的票数即可，对于第k个人后面的人，按相同思路再累加给count即可。
class Solution {
public:int timeRequiredToBuy(vector<int>& tickets, int k) {int count = 0; //用于记录时间int n = tickets.size();for (int i = 0; i < n; i++){if (i <= k){count += min(tickets[i], tickets[k]);}else{count += min(tickets[i], tickets[k] - 1);}}return count;}
};