腾讯云服务器免费领取试用,sem优化怎么做,怎么还原wordpress,动易与php环境架设网站一、二叉搜索树的最小绝对差
1.题目
Leetcode#xff1a;第 530 题
给你一个二叉搜索树的根节点 root #xff0c;返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数#xff0c;其数值等于两值之差的绝对值。 示例 1#xff1a; 输入#xff1a;root [4,2,…一、二叉搜索树的最小绝对差
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:vectorint 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) {stackTreeNode* 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用于记录遍历过程中前一个访问的节点。vectorint 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是二叉树的根节点指针。vectorint findMode(TreeNode* root) {count 0; // 重置当前连续元素数量。maxCount 0; // 重置最大连续元素数量。pre NULL; // 重置前一个访问的节点指针。result.clear(); // 清空结果为新的搜索做准备。searchBST(root); // 调用searchBST函数传入根节点开始递归遍历。return result;// 返回结果result包含出现次数最多的元素。}
};// 二、查找二叉搜索树中的众数迭代法。
class Solution2 {
public:// 定义一个名为findMode的公共成员函数用于启动搜索过程并返回出现次数最多的元素列表。// 参数root是二叉树的根节点指针。vectorint findMode(TreeNode* root) {stackTreeNode* st; // 定义一个栈st用于存放二叉树的节点指针辅助进行迭代遍历。TreeNode* cur root; // 定义一个当前节点指针cur初始指向根节点。TreeNode* pre NULL; // 定义一个前一个节点指针pre初始为NULL用于记录遍历过程中的前一个节点值。int maxCount 0; // 初始化最大连续元素数量maxCount为0。int count 0; // 初始化当前连续元素数量count为0。vectorint 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以上皆是本人在探索算法旅途中的浅薄见解诚挚地希望得到各位的宝贵意见与悉心指导若有不足或谬误之处还请多多指教。
