0.引言
● 530.二叉搜索树的最小绝对差
● 501.二叉搜索树中的众数
● 236. 二叉树的最近公共祖先
530. 二叉搜索树的最小绝对差
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Easy (63.51%) | 438 | - |
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
image.png
输入：root = [4,2,6,1,3]
输出：1
示例 2：
image.png
输入：root = [1,0,48,null,null,12,49]
输出：1
提示：
- 树中节点的数目范围是
[2, 10<sup>4</sup>] 0 <= Node.val <= 10<sup>5</sup>
注意：本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
递归法
第一想法是最小的差值出现在最小二叉搜索树单元里面，其实是错误的：
/*
* @lc app=leetcode.cn id=530 lang=cpp
*
* [530] 二叉搜索树的最小绝对差
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
int res = std::numeric_limits<int>::max();
dfs(root, res);
return res;
}
private:
void dfs(TreeNode* node, int& min_diff) {
if (node == nullptr) return;
if (node->left) {
int diff = std::abs(node->val - node->left->val);
if (diff < min_diff) {
min_diff = diff;
}
}
if (node->right) {
int diff = std::abs(node->val - node->right->val);
if (diff < min_diff) {
min_diff = diff;
}
}
dfs(node->left, min_diff);
dfs(node->right, min_diff);
}
};
// @lc code=end
只计算了当前节点与其直接的左右子节点之间的差值，但是没有考虑到最小绝对差可能出现在其他位置的情况。可以在遍历二叉搜索树的过程中记录前一个遍历到的节点，以便计算正确的最小绝对差。
/*
* @lc app=leetcode.cn id=530 lang=cpp
*
* [530] 二叉搜索树的最小绝对差
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
int res = std::numeric_limits<int>::max();
TreeNode* prev = nullptr;
dfs(root, prev, res);
return res;
}
private:
// 中序遍历
void dfs(TreeNode* node, TreeNode*& prev, int& min_diff) {
if (node == nullptr) return;
dfs(node->left, prev, min_diff);
if (prev != nullptr) {
int diff = std::abs(node->val - prev->val);
if (diff < min_diff) {
min_diff = diff;
}
}
prev = node;
dfs(node->right, prev, min_diff);
}
};
// @lc code=end
第二种思路，遍历一遍用vector存下来就是有序数组，然后再依次看diff.
501.二叉搜索树中的众数
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Easy (54.42%) | 609 | - |
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
image.png
输入：root = [1,null,2,2]
输出：[2]
示例 2：
输入：root = [0]
输出：[0]
提示：
- 树中节点的数目在范围
[1, 10<sup>4</sup>]内 -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
递归法
排序折腾一点：
/*
* @lc app=leetcode.cn id=501 lang=cpp
*
* [501] 二叉搜索树中的众数
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> findMode(TreeNode* root) {
std::vector<int> res;
std::unordered_map<int, int> record_map;
dfs(root, record_map);
if (record_map.empty()) return {};
std::vector<PAIR> record_vec;
for (const auto& element : record_map) {
record_vec.push_back(std::make_pair(element.second, element.first));
}
std::sort(
record_vec.begin(), record_vec.end(),
[](const PAIR& lhs, const PAIR& rhs) { return lhs.first > rhs.first; });
int max_count = record_vec.begin()->first;
for (const auto& element : record_vec) {
if (element.first == max_count) {
res.push_back(element.second);
}
}
return res;
}
private:
using PAIR = std::pair<int, int>;
void dfs(TreeNode* node, std::unordered_map<int, int>& record_map) {
if (node == nullptr) {
return;
}
// 前序遍历
record_map[node->val]++;
dfs(node->left, record_map);
dfs(node->right, record_map);
}
};
// @lc code=end
完全是当一个数组在处理了，肯定是复杂了，挖坑。
236. # 二叉树的最近公共祖先
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (69.62%) | 2198 | - |
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
image.png
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
image.png
输入：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, 10<sup>5</sup>]内。 -10<sup>9</sup> <= Node.val <= 10<sup>9</sup>- 所有
Node.val互不相同。 p != q-
p和q均存在于给定的二叉树中。
递归法
/*
* @lc app=leetcode.cn id=236 lang=cpp
*
* [236] 二叉树的最近公共祖先
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return root;
std::vector<TreeNode*> path_p; // 存储节点路径，模拟栈
std::vector<TreeNode*> path_q;
dfs(root, p, path_p);
dfs(root, q, path_q);
std::stack<TreeNode*> res;
int sz = path_p.size() < path_q.size() ? path_p.size() : path_q.size();
for (int i = 0; i < sz; i++) {
if (path_p[i] == path_q[i]) {
res.push(path_p[i]);
}
}
return res.top(); // 离根节点最远的那个节点
}
private:
bool dfs(TreeNode* root, TreeNode* target_node,
std::vector<TreeNode*>& path) {
if (!root) return false;
path.push_back(root); // 前序
if (target_node == root) return true;
if (dfs(root->left, target_node, path)) return true;
if (dfs(root->right, target_node, path)) return true;
path.pop_back(); // 回溯，恢复
return false;
}
};
// @lc code=end
