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]

解题思路：

常用思路：

1. 使用中序遍历获得每个元素及其出现次数，用哈希表保存；
2. 对哈希表中元素按照出现次数由大到小进行排序；
3. 取前边出现次数最大的元素作为答案

优化思路：

1. 使用变量maxCount表示出现的最大次数，count记录当前遍历元素出现次数；
2. pre指针不能作为形参，只能定义在函数外作为全局变量，因为pre永远指向当前节点的上一个节点处。
3. 每一层递归中，将count与maxCount进行比较，若count较大，则清空数组中之前已保存的元素，重新写入新元素，二者相等则向数组中继续添加元素。

代码：

常用思路：

class Solution { public:     void traversal(TreeNode* root, unordered_map& hash)     {         if(root == nullptr) return;         traversal(root->left,hash);         hash[root->val]++;         traversal(root->right,hash);     }      bool static cmp (const pair& a, const pair& b)      {         return a.second > b.second;     }      vector findMode(TreeNode* root) {         unordered_map hash;         traversal(root,hash);         vector result;         vector> 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& 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 findMode(TreeNode* root) {         vector 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。因为根据定义最近公共祖先节点可以为节点本身。

解题思路：

两种情况

1. p=7,q=4-->p,q分别为左右子树中的节点，2是二者公共祖先
2. p=7,q=2-->q是p的祖先，q是二者公共祖先

使用后序遍历，三种返回结果

1. 左右子树返回结果均不为空，则返回两颗子树的根节点，该根节点为p，q的公共祖先节点；
2. 有一颗子树返回结果不为空，则返回该子树函数递归结果，此时函数递归结果表示p，q公共祖先节点；
3. 左右子树返回结果都为空，返回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;     } };