530.二叉搜索树的最小绝对差
题目链接 文章讲解 视频讲解
关键词： 二叉搜索树 --> 中序遍历
关于递归的返回值
由于需要遍历整棵二叉树，所以返回值为void，如果不是遍历整棵二叉树，需要在得到结果时立即返回结果，此时返回值才不为空
怎样使用两个指针pre和cur使得pre始终指向cur的前一个节点？
- 中序搜索，cur指向的第一个节点是左子树最左边的节点，而cur的前一个节点是nullptr，所以pre应初始化为nullptr
- 回溯时(中序处理时)cur要指向下一个节点，所以应该在cur指向下一个节点前(进行下一层递归前)将pre指向cur当前的位置
class Solution {
private:
int minValue = INT_MAX;
TreeNode* pre = nullptr;
public:
int getMinimumDifference(TreeNode* root) {
traversal(root);
return minValue;
}
// 二叉搜索树，中序遍历保持顺序
void traversal(TreeNode* cur) {
if(cur == nullptr) return ;
// 中序遍历左子树
traversal(cur->left);
// 保存最小值
if(pre) minValue = min(minValue, cur->val - pre->val);
// 回溯前保存cur的值保证pre始终指向cur的前一个节点
pre = cur;
// 中序遍历右子树
traversal(cur->right);
}
};
501.二叉搜索树中的众数
方法一 哈希表
需要遍历两次
思路：中序遍历二叉搜索树，用map记录每个数字出现的频率，并记录最高频率
遍历map将频率最高的数字保存在结果集中
class Solution {
private:
// 记录最高频率
int count = 0;
public:
vector<int> findMode(TreeNode* root) {
vector<int> ans;
unordered_map<int, int> map;
traversal(root, map);
// 遍历map，如果频率是最高的，则将结果保存在结果集中
for(auto pair : map) {
if(pair.second == count) ans.push_back(pair.first);
}
return ans;
}
void traversal(TreeNode* node, unordered_map<int, int>& map) {
if(node == nullptr) return ;
// 中序遍历左子树
traversal(node->left, map);
// 使用哈希表保存每个数出现的频率
map[node->val]++;
// 更新最高频率
count = max(count, map[node->val]);
// 中序遍历右子树
traversal(node->right, map);
}
};
方法二 双指针
只需遍历一遍
trick: 遍历的同时将满足要求的数加入结果集，如果最高频率发生变化时，则清空结果集重新添加满足要求的数
class Solution {
private:
int count, maxCount = 0;
TreeNode* pre = nullptr;
public:
vector<int> findMode(TreeNode* root) {
vector<int> ans;
traversal(root, ans);
return ans;
}
void traversal(TreeNode* cur, vector<int>& ans) {
if(cur == nullptr) return ;
// 中序遍历左子树
traversal(cur->left, ans);
// 处理逻辑
// 当pre == nullptr时，此时遇到第一个节点，将count更新为1
if(pre == nullptr) count = 1;
// 如果前一个值和当前值不相等，则更新count记录新值的频率
else if(pre->val != cur->val) {
count = 1;
} else { // 如果当前值和前一个值相等，则count值加一
count++;
}
// 如果count值和最高频率相等则将当前值保存到结果集中
if(count == maxCount) ans.push_back(cur->val);
// 如果count > maxCount 则将maxCount更新，并将结果集清空，将当前值假如结果集中
else if(count > maxCount) {
maxCount = count;
ans.clear();
ans.push_back(cur->val);
}
pre = cur;
// 中序遍历右子树
traversal(cur->right, ans);
}
};
236.二叉树的最近公共祖先
求公共祖先需要从下往上查找所以应该选择后续遍历
判断逻辑：如果递归遍历遇到q，就将q返回，遇到p 就将p返回，那么如果 左右子树的返回值都不为空，说明此时的中节点，一定是q 和p 的最近祖先。
如果q是p的祖先或者p是q的祖先，那么只要遇到其中一个就返回的逻辑已经满足了这种情况
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr) return nullptr;
if(root == p || root == q) return root;
// 后序遍历左子树
TreeNode* left = lowestCommonAncestor(root->left, p, q);
// 后序遍历右子树
TreeNode* right = lowestCommonAncestor(root->right, p, q);
// 处理逻辑
if(left == nullptr && right != nullptr) return right;
if(left != nullptr && right == nullptr) return left;
if(left != nullptr && right != nullptr) return root;
else return nullptr;
}
};