一、参考资料
二叉搜索树的最小绝对差
视频讲解:https://www.bilibili.com/video/BV1DD4y11779
二叉搜索树中的众数
视频讲解:https://www.bilibili.com/video/BV1fD4y117gp
二叉树的最近公共祖先
视频讲解:https://www.bilibili.com/video/BV1jd4y1B7E2
二、LeetCode530.二叉搜索树的最小绝对差
https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/
示例一:
![](/i/ll/?i=img_convert/23ae2aa6e4029749b48634a3ebd4ac8f.jpeg)
示例二:
![](/i/ll/?i=img_convert/b66c4df8e5ba5dafad7daa99adfeca0a.jpeg)
给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数,其数值等于两值之差的绝对值。
示例 1:
输入:root = [4,2,6,1,3] 输出:1
示例 2:
输入:root = [1,0,48,null,null,12,49] 输出:1
提示:
树中节点的数目范围是 [2, 10^4]
0 <= Node.val <= 10^5
注意:本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
- /**
- * 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 res = INT_MAX;
- TreeNode* pre = NULL; // pre节点记录一下cur节点的前一个节点
- void traversal(TreeNode* cur) {
- if (cur == NULL) return ;
- traversal(cur->left);
- if (pre != NULL) {
- res = min(res, cur->val - pre->val);
- }
- pre = cur;
- traversal(cur->right);
- }
- int getMinimumDifference(TreeNode* root) {
- // 递归法解决
- traversal(root);
- return res;
- }
- };
![](/i/ll/?i=img_convert/e0872568f85b3ff3804ea8d73fcc3b13.png)
迭代法:
- /**
- * 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) {
- stack<TreeNode*> st;
- TreeNode* cur = root;
- TreeNode* pre = NULL;
- int res = INT_MAX;
- while (cur != NULL || !st.empty()) {
- if (cur != NULL) { // 指针来访问节点,访问到最底层
- st.push(cur); // 将访问的节点放进栈
- cur = cur->left; // 左
- } else {
- cur = st.top();
- st.pop();
- if (pre != NULL) {
- res = min(res, cur->val - pre->val);
- }
- pre = cur;
- cur = cur->right;
- }
- }
- return res;
- }
- };
卡哥总结:
遇到在二叉搜索树上求什么最值,求差值之类的,都要思考一下二叉搜索树可是有序的,要利用好这一特点。同时要学会在递归遍历的过程中如何记录前后两个指针,这也是一个小技巧,学会了还是很受用的。
三、LeetCode501.二叉搜索树中的众数
https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
示例1:
![](/i/ll/?i=img_convert/b655a54d0ef68ef4ff98840257bebfc7.jpeg)
给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
示例 1:
输入:root = [1,null,2,2] 输出:[2]
示例 2:
输入:root = [0] 输出:[0]
提示:
树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105
![](/i/ll/?i=img_convert/b7df3574a9601335b1f6730d525f66d3.png)
(只需要遍历一遍二叉搜索树,就求出了众数的集合)
- // 卡哥代码(详细注释版)
- class Solution {
- private:
- int maxCount = 0; // 最大频率
- int count = 0; // 统计频率
- TreeNode* pre = NULL;
- vector<int> result;
- void searchBST(TreeNode* cur) {
- if (cur == NULL) return ;
- searchBST(cur->left); // 左
- // 中
- if (pre == NULL) { // 第一个节点
- count = 1;
- } else if (pre->val == cur->val) { // 与前一个节点数值相同
- count++;
- } else { // 与前一个节点数值不同
- count = 1;
- }
- pre = cur; // 更新上一个节点
- if (count == maxCount) { // 如果和最大值相同,放进result中
- result.push_back(cur->val);
- }
- if (count > maxCount) { // 如果计数大于最大值频率
- maxCount = count; // 更新最大频率
- result.clear(); // 很关键的一步,不要忘记清空result,之前result里的元素都失效了
- result.push_back(cur->val);
- }
- searchBST(cur->right); // 右
- return ;
- }
- public:
- vector<int> findMode(TreeNode* root) {
- count = 0;
- maxCount = 0;
- TreeNode* pre = NULL; // 记录前一个节点
- result.clear();
- searchBST(root);
- return result;
- }
- };
- // version1:普通二叉树,递归法
- class Solution {
- private:
- // 前序遍历
- void searchBST(TreeNode* cur, unordered_map<int, int>& map) {
- if (cur == NULL) return ;
- map[cur->val]++;
- searchBST(cur->left, map);
- searchBST(cur->right, map);
- return ;
- }
- bool static cmp(const pair<int, int>& a, const pair<int, int>& b) {
- return a.second > b.second;
- }
- public:
- vector<int> findMode(TreeNode* root) {
- unordered_map<int, int> map; // key: 元素,value:出现频率
- vector<int> res;
- if (root == NULL) return res;
- searchBST(root, map);
- vector<pair<int, int>> vec(map.begin(), map.end());
- sort(vec.begin(), vec.end(), cmp); // 给频率排序
- res.push_back(vec[0].first);
- for (int i = 1; i < vec.size(); i++) {
- // 取最高的放到res数组中
- if (vec[i].second == vec[0].second) res.push_back(vec[i].first);
- else break;
- }
- return res;
- }
- };
- // version2:二叉搜索树,只需要遍历一遍,就求出众数的集合
- class Solution {
- private:
- int maxCount = 0; // 最大频率
- int count = 0; // 统计频率
- TreeNode* pre = NULL;
- vector<int> res;
- void searchBST(TreeNode* cur) {
- if (cur == NULL) return ;
- searchBST(cur->left); // 左
- // 中
- if (pre == NULL) { // 第一个节点
- count = 1;
- } else if (pre->val == cur->val) { // 与前一个节点数值相同
- count ++;
- } else { // 与前一个节点数值不同
- count = 1;
- }
- pre = cur; // 更新上一个节点
- // 如果和最大值相同,放进result中
- if (count == maxCount) {
- res.push_back(cur->val);
- }
- // 如果计数大于最大值频率
- if (count > maxCount) {
- maxCount = count; // 更新最大频率
- res.clear(); // 很关键的一步,不要忘记清空Result数组
- res.push_back(cur->val);
- }
- searchBST(cur->right); // 右
- }
- public:
- vector<int> findMode(TreeNode* root) {
- count = 0;
- maxCount = 0;
- TreeNode* pre = NULL; // 记录前一个节点
- res.clear();
- searchBST(root);
- return res;
- }
- };
- // 我写的,简化版
- class Solution {
- private:
- vector<int> res;
- int count = 0;
- int maxCount = 0;
- TreeNode* pre = NULL;
- void searchBST(TreeNode* cur) {
- if (cur == NULL) return ;
- searchBST(cur->left);
- if (pre == NULL) count = 1;
- else if (pre->val == cur->val) count++;
- else count = 1;
- pre = cur; // 更新pre !!!很重要
- // 这里一定不能合并下面的两个if,假如和原来相等的count,那么clear操作会清楚原来的数值
- if (count == maxCount) res.push_back(cur->val);
- if (count > maxCount) {
- maxCount = count;
- res.clear();
- res.push_back(cur->val);
- }
- searchBST(cur->right);
- }
- public:
- vector<int> findMode(TreeNode* root) {
- searchBST(root);
- return res;
- }
- };
迭代法:
- // version3: 迭代法
- class Solution {
- public:
- vector<int> findMode(TreeNode* root) {
- stack<TreeNode*> st;
- TreeNode* cur = root;
- TreeNode* pre = NULL;
- vector<int> res;
- int count = 0;
- int maxCount = 0;
- while (cur != NULL || !st.empty()) {
- if (cur != NULL) {
- st.push(cur);
- cur = cur->left;
- } else {
- cur = st.top();
- st.pop();
- if (pre == NULL) count = 1;
- else if (pre->val == cur->val) count++;
- else count = 1;
- pre = cur;
- if (count == maxCount) {
- res.push_back(cur->val);
- }
- if (count > maxCount) {
- maxCount = count;
- res.clear();
- res.push_back(cur->val);
- }
- cur = cur->right;
- }
- }
- return res;
- }
- };
后面我又分别用递归和迭代独立实现了一遍~代码就不贴了
四、LeetCode236. 二叉树的最近公共祖先
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
示例一:
![](/i/ll/?i=img_convert/f7c6652521eb602db752d8860b4a42c5.png)
示例二:
![](/i/ll/?i=img_convert/2e750e6f74326ec447025eab3ad9a2eb.png)
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大( 一个节点也可以是它自己的祖先)。”
示例 1:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2:
输入: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^5] 内。
-10^9 <= Node.val <= 10^9
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
- // 我根据视频讲解思路理解写的代码:
- /**
- * 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 == NULL || root == p || root == q) return root;
- TreeNode* left = lowestCommonAncestor(root->left, p, q);
- TreeNode* right = lowestCommonAncestor(root->right, p, q);
- if (left != NULL && right != NULL) return root;
- else if (left == NULL && right != NULL) return right;
- else if (left != NULL && right == NULL) return left;
- else return NULL;
- }
- };
在递归函数有返回值的情况下:如果要搜索一条边,递归函数返回值不为空的时候,立刻返回,如果搜索整个树,直接用一个变量left、right接住返回值,这个left、right后序还有逻辑处理的需要,也就是后序遍历中处理中间节点的逻辑(也是回溯)。
![](/i/ll/?i=img_convert/2327ebc0f068db31c031e4ecb212240b.png)
如果left 和 right都不为空,说明此时root就是最近公共节点。这个比较好理解
如果left为空,right不为空,就返回right,说明目标节点是通过right返回的,反之依然。
![](/i/ll/?i=img_convert/271ebcf18bd5b7aaca60b7a37f010a67.png)
图中节点10的左子树返回null,右子树返回目标值7,那么此时节点10的处理逻辑就是把右子树的返回值(最近公共祖先7)返回上去!
这里也很重要,可能刷过这道题目的同学,都不清楚结果究竟是如何从底层一层一层传到头结点的。
那么如果left和right都为空,则返回left或者right都是可以的,也就是返回空。
寻找最小公共祖先,完整流程图如下:
![](/i/ll/?i=img_convert/6a22923820f965ce6da83c20980a5cf2.png)
- // 精简版
- class Solution {
- public:
- TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
- if (root == q || root == p || root == NULL) return root;
- TreeNode* left = lowestCommonAncestor(root->left, p, q);
- TreeNode* right = lowestCommonAncestor(root->right, p, q);
- if (left != NULL && right != NULL) return root;
- if (left == NULL) return right;
- return left;
- }
- };
卡哥总结:对回溯的理解,以及结果是如何一层一层传递上去的,有三点归纳:
求最小公共祖先,需要从底向上遍历,那么二叉树,只能通过后序遍历(即:回溯)实现从底向上的遍历方式。
在回溯的过程中,必然要遍历整棵二叉树,即使已经找到结果了,依然要把其他节点遍历完,因为要使用递归函数的返回值(也就是代码中的left和right)做逻辑判断。
要理解如果返回值left为空,right不为空为什么要返回right,为什么可以用返回right传给上一层结果。
最后,本题没有给出迭代法,因为迭代法不适合模拟回溯的过程。
总结:
状态还不错哈,对递归和回溯有了更多的认识,多复习哈,还有就是记得看自己写的一些注释。
昨天补完了三天的题,今天补完所有博客,再把最后一节树的题目做完,争取完结撒花~
刷题加油鸭~~
标签:right,TreeNode,cur,随想录,二叉,搜索,NULL,root,left From: https://www.cnblogs.com/ucaszym/p/17093596.html