Day 21 二叉树
530. 二叉搜索树的最小绝对差
递归
递归中保存前一个节点的指针的方法，需要再学习，巩固一下
class Solution {
int minDiff = INT_MAX;
TreeNode *pre = nullptr;
void traverse(TreeNode *root)
{
if (!root) return;
traverse(root->left);
if (pre)
{
int curDiff = abs(root->val - pre->val);
if (curDiff < minDiff)
{
minDiff = curDiff;
}
}
pre = root;
traverse(root->right);
}
public:
int getMinimumDifference(TreeNode* root) {
traverse(root);
return minDiff;
}
};
迭代
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
stack<TreeNode*> stk;
TreeNode *pNode = root;
int pre = INT_MAX, minDiff = INT_MAX;
while (pNode || !stk.empty())
{
if (pNode)
{
stk.push(pNode);
pNode = pNode->left;
}
else
{
pNode = stk.top();
stk.pop();
int curDiff = abs(pNode->val - pre);
if (curDiff < minDiff)
{
minDiff = curDiff;
}
pre = pNode->val;
pNode = pNode->right;
}
}
return minDiff;
}
};
501. 二叉搜索树中的众数
一下子就想到的方法：遍历一遍二叉搜索树，把各个节点的值存进哈希表里（节点值——键，出现频率——值），再遍历哈希表找众数
一般方法
class Solution {
public:
vector<int> findMode(TreeNode* root) {
unordered_map<int, int> table;
stack<TreeNode*> stk;
TreeNode *cur = root;
while (cur || !stk.empty())
{
if (cur)
{
stk.push(cur);
cur = cur->left;
}
else
{
cur = stk.top();
stk.pop();
table[cur->val]++;
cur = cur->right;
}
}
vector<int> rst;
int time = 0;
for (auto &[key, val] : table)
{
if (val > time)
{
time = val;
rst.clear();
rst.push_back(key);
}
else if (val == time)
{
rst.push_back(key);
}
}
return rst;
}
};
既然是二叉搜索树，中序遍历就是有序的。有序的话，我们就有希望在线性时间内完成找众数的操作（因为相同的数字都扎堆连在一起）
递归
class Solution {
vector<int> rst;
TreeNode *pre = nullptr;
int maxTime = 0, curTime = 0;
void traverse(TreeNode *root)
{
if (!root) return;
traverse(root->left);
if (pre)
{
if (pre->val == root->val)
{
curTime++;
}
else
{
curTime = 1;
}
}
else // 是访问的第一个节点
{
curTime = 1;
}
pre = root;
if (curTime > maxTime)
{
maxTime = curTime;
rst.clear();
rst.push_back(pre->val);
}
else if (curTime == maxTime)
{
rst.push_back(pre->val);
}
traverse(root->right);
}
public:
vector<int> findMode(TreeNode* root) {
traverse(root);
return rst;
}
};
迭代
class Solution {
public:
vector<int> findMode(TreeNode* root) {
vector<int> rst;
int maxTime = 0, curTime = 0;
stack<TreeNode*> stk;
TreeNode *cur = root, *pre = nullptr;
while (cur || !stk.empty())
{
if (cur)
{
stk.push(cur);
cur = cur->left;
}
else
{
cur = stk.top();
stk.pop();
if (pre)
{
if (pre->val == cur->val)
{
curTime++;
}
else
{
curTime = 1;
}
}
else
{
curTime = 1;
}
pre = cur;
if (curTime > maxTime)
{
maxTime = curTime;
rst.clear();
rst.push_back(cur->val);
}
else if (curTime == maxTime)
{
rst.push_back(cur->val);
}
cur = cur->right;
}
}
return rst;
}
};
236. 二叉树的最近公共祖先
偷偷看了一点提示，应该是用后序遍历，先处理子树，再到根节点，如果两棵子树返回包含两个目标节点的提示，该节点就是公共祖先节点
（要能想到是后序遍历，思路就打开了）文章来源：https://www.toymoban.com/news/detail-579888.html
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;
TreeNode *leftRst = lowestCommonAncestor(root->left, p, q);
TreeNode *rightRst = lowestCommonAncestor(root->right, p, q);
if (root == p || root == q) // 如果根节点是p或q其中一个，可以直接返回
{
return root;
}
if (leftRst && rightRst) // 如果左右子树都不为空，那么该节点必定为最近公共祖先节点
{
return root;
}
return leftRst ? leftRst : rightRst; // 左子树不为空则返回左子树，否则不管右子树是否为空，都返回
}
};
上面的代码是简化后的版本，隐藏了很多思考的细节，下面贴一下我按照自己的思路写的第一个版本文章来源地址https://www.toymoban.com/news/detail-579888.html
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;
TreeNode *leftRst = lowestCommonAncestor(root->left, p, q);
TreeNode *rightRst = lowestCommonAncestor(root->right, p, q);
if (!leftRst && !rightRst) // 如果左右子树都为空
{
if (root == p) // 根节点恰好是q或者p,可以返回根节点
{
return p;
}
else if (root == q)
{
return q;
}
else return nullptr; // 如果都不是,也要返回空
}
if (leftRst && rightRst) // 如果左右子树都不为空，那么该节点必定为最近公共祖先节点
{
return root;
}
if (root == p || root == q) // 如果根节点是p或者q中的一个,返回根节点
{
return root;
}
return leftRst ? leftRst : rightRst; // 返回q和p中不是空的那个节点
}
// 以上所有的可能情况都被一一列举出来,比较方便理解
};
到了这里，关于算法刷题Day 21 二叉搜索树的最小绝对差+二叉搜索树中的众数+二叉树的最近公共祖先的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
