网站建设现状调查研究,网app开发,wordpress如何换域名,上海一网通办目录
二叉搜索树的最小绝对差二叉搜索树中的众数二叉树的最近公共祖先额外练手题目
题目1、二叉搜索树的最小绝对差
力扣题目链接(opens new window)
给你一棵所有节点为非负值的二叉搜索树#xff0c;请你计算树中任意两节点的差的绝对值的最小值。
示例#xff1a; 思…目录
二叉搜索树的最小绝对差二叉搜索树中的众数二叉树的最近公共祖先额外练手题目
题目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 result
C
class Solution {
private:
vectorint 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;vectorint 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:vectorint 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(vectorint 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;}
};
