阅读量:0
530.二叉搜索树的最小绝对差
题目链接：. - 力扣（LeetCode）
讲解视频：二叉搜索树中，需要掌握如何双指针遍历！| LeetCode：530.二叉搜索树的最小绝对差
题目描述：
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1
解题思路：
该题用到了二叉搜索树的性质：中序遍历元素单调递增排序。
因此本题就转变成中序遍历二叉树求相邻两节点差值的最小值
受昨天题目--98.验证二叉搜索树的启发，该题目使用双指针法进行遍历可以降低计算量
代码：
class Solution { public: int minVal = INT_MAX; TreeNode* pre = nullptr; int getMinimumDifference(TreeNode* root) { if(root == nullptr) return 0; getMinimumDifference(root->left); if(pre) { int t = root->val - pre->val; minVal = minVal > t ? t : minVal; } pre = root; getMinimumDifference(root->right); return minVal; } };501.二叉搜索树中的众数
题目链接：. - 力扣（LeetCode）
讲解视频：不仅双指针，还有代码技巧可以惊艳到你！ | LeetCode：501.二叉搜索树中的众数
题目描述：
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2] 输出：[2]
解题思路：
常用思路：
- 使用中序遍历获得每个元素及其出现次数，用哈希表保存；
- 对哈希表中元素按照出现次数由大到小进行排序；
- 取前边出现次数最大的元素作为答案
优化思路：
- 使用变量maxCount表示出现的最大次数，count记录当前遍历元素出现次数；
- pre指针不能作为形参，只能定义在函数外作为全局变量，因为pre永远指向当前节点的上一个节点处。
- 每一层递归中，将count与maxCount进行比较，若count较大，则清空数组中之前已保存的元素，重新写入新元素，二者相等则向数组中继续添加元素。
代码：
常用思路：
class Solution { public: void traversal(TreeNode* root, unordered_map<int,int>& hash) { if(root == nullptr) return; traversal(root->left,hash); hash[root->val]++; traversal(root->right,hash); } bool static cmp (const pair<int, int>& a, const pair<int, int>& b) { return a.second > b.second; } vector<int> findMode(TreeNode* root) { unordered_map<int,int> hash; traversal(root,hash); vector<int> result; vector<pair<int,int>> vii(hash.begin(),hash.end()); sort(vii.begin(),vii.end(),cmp); int t = 0; while(t < vii.size() && vii[t].second == vii[0].second) result.push_back(vii[t].first), t++; return result; } };优化思路：
class Solution { public: int maxCount = 0; int count = 0; TreeNode* pre = nullptr; void traversal(TreeNode* root, vector<int>& result) { if(root == nullptr) return; traversal(root->left,result); if(pre == nullptr) count = 1; else if(pre->val == root->val) count++; else count = 1; pre = root; if(count == maxCount) result.push_back(root->val); if(count > maxCount) { maxCount = count; result.clear(); result.push_back(root->val); } traversal(root->right,result); return; } vector<int> findMode(TreeNode* root) { vector<int> result; traversal(root,result); return result; } };236. 二叉树的最近公共祖先
题目链接：. - 力扣（LeetCode）
讲解视频：自底向上查找，有点难度！ | LeetCode：236. 二叉树的最近公共祖先
题目描述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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和节点4的最近公共祖先是节点5。因为根据定义最近公共祖先节点可以为节点本身。
解题思路：
两种情况
- p=7,q=4-->p,q分别为左右子树中的节点，2是二者公共祖先
- p=7,q=2-->q是p的祖先，q是二者公共祖先
使用后序遍历，三种返回结果
- 左右子树返回结果均不为空，则返回两颗子树的根节点，该根节点为p，q的公共祖先节点；
- 有一颗子树返回结果不为空，则返回该子树函数递归结果，此时函数递归结果表示p，q公共祖先节点；
- 左右子树返回结果都为空，返回nullptr。
代码：
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root == nullptr || 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 && !right) return left; else if(!left && right) return right; else return nullptr; } };