530. 二叉搜索树的最小绝对差
题目链接：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/
算法思想：
因为是二叉搜索树，因此采用中序遍历的话，是有序的。采用一个前指针指向前一个节点，和当前节点进行比较。
代码：
class Solution {
public:
TreeNode* pre=NULL;
int min = INT_MAX;
void getmindata(TreeNode* root)
{
if (root==NULL)
return;
getmindata(root->left);
if(pre!=NULL&&abs(root->val-pre->val)<min)
{
min = abs(root->val-pre->val);
}
pre = root;
getmindata(root->right);
}
int getMinimumDifference(TreeNode* root) {
getmindata(root);
return min;
}
};
501. 二叉搜索树中的众数
题目链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree/
算法思想：
使用一个max_count记录当前位置的最大值，count记录当前元素的最大值。vec记录当前记录的元素、
当最大值更新的时候，vec清空，重新加入众数对应的元素，如果最大值和count相同，直接加入。
class Solution {
public:
TreeNode* pre=NULL;
int count = 0;
int max_count = 0;
vector<int> res;
void inorder(TreeNode* root)
{
if(root==NULL)
{
return;
}
inorder(root->left);
if(pre==NULL) // 前一个节点为空
{
count = 1;
}
else if(pre->val == root->val)
count++;
else
count = 1; //和前一个节点相同
pre = root;
if(count == max_count)
{
res.push_back(root->val);
}
if(max_count<count)
{
res.clear();
max_count = count;
res.push_back(root->val);
}
inorder(root->right);
}
vector<int> findMode(TreeNode* root) {
inorder(root);
return res;
}
};
236. 二叉树的最近公共祖先
题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
算法思想：
采用后序遍历。终止条件：遇到p或者q就返回。
如果左子树和右子树都找到了p或者q，则root为最近的公共祖先。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL)
return NULL;
if(root==p ||root==q)
return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left&&right)
return root;
else if(left)
return left;
else
return right;
}
};
