题目1:530. 二叉搜索树的最小绝对差 - 力扣(LeetCode)
class Solution {
public:
int reslut = INT_MAX;
TreeNode* pre = NULL;
void trackingback(TreeNode* node) {
if(node == NULL) return;
trackingback(node->left);
if(pre != NULL) {
reslut = min(reslut, node->val - pre->val);
}
pre = node;
trackingback(node->right);
}
int getMinimumDifference(TreeNode* root) {
trackingback(root);
return reslut;
}
};
题目2:501. 二叉搜索树中的众数 - 力扣(LeetCode)
// 中序遍历用map记录每个数出现的个数,然后找最大的
class Solution {
public:
unordered_map<int, int> map;
void trackingback(TreeNode* node) {
if(node == NULL) return;
trackingback(node->left);
if(map.find(node->val) != map.end()) {
map[node->val]++;
}else {
map.insert(pair<int, int>(node->val, 1));
}
trackingback(node->right);
}
vector<int> findMode(TreeNode* root) {
vector<int> reslut;
trackingback(root);
int num = 1;
for(auto iter =map.begin();iter != map.end();iter++) {
if(iter->second > num) {
num = iter->second;
}
}
for(auto iter =map.begin();iter != map.end();iter++) {
if(iter->second == num) {
reslut.push_back(iter->first);
}
}
return reslut;
}
};
在递归里操作,主要就是更新maxcount 然后要把reslut也更新
class Solution {
public:
vector<int> reslut;
int count = 0;
int maxcount = 0;
TreeNode* pre = NULL;
void trackingback(TreeNode* node) {
if(node == NULL) return;
trackingback(node->left);
if(pre == NULL) {
count = 1;
}else if(pre->val == node->val) {
count++ ;
}else if(pre->val != node->val) {
count = 1;
}
pre = node;
if(count == maxcount) {
reslut.push_back(node->val);
}
if(count > maxcount) {
reslut.clear();
maxcount = count;
reslut.push_back(node->val);
}
trackingback(node->right);
}
vector<int> findMode(TreeNode* root) {
trackingback(root);
return reslut;
}
};
题目3:236. 二叉树的最近公共祖先 - 力扣(LeetCode)
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL) return NULL;
if(root == p || root == q) return root;
TreeNode* leftnode = lowestCommonAncestor(root->left, p, q);
TreeNode* rightnode = lowestCommonAncestor(root->right, p, q);
if(rightnode != NULL && leftnode != NULL) return root;
else if(rightnode == NULL && leftnode != NULL) return leftnode;
else if(rightnode != NULL && leftnode == NULL) return rightnode;
else return NULL;
}
};