代码随想录day21

530. 二叉搜索树的最小绝对差

解题步骤：

1、将二叉搜索树转化为有序数组；

2、按照重新排序后的数组进行遍历，获取最小的绝对值差。

 1 class Solution {
 2 private:
 3     //将二叉搜索树转化为一个有序数组
 4     vector<int> vec;
 5     void travesal(TreeNode* root){
 6         if (root == nullptr) return;
 7         travesal(root->left);
 8         vec.push_back(root->val);
 9         travesal(root->right);
10     }
11 public:
12     int getMinimumDifference(TreeNode* root) {
13         int result = INT_MAX;
14         vec.clear();
15         travesal(root);
16         for (int i = 1; i < vec.size(); i++){
17             result = result < vec[i] - vec[i - 1] ? result : vec[i] - vec[i - 1];
18         }
19         return result;
20     }
21 };

501. 二叉搜索树中的众数

 1 class Solution {
 2 private:
 3     int maxCount = 0; // 最大频率
 4     int count = 0; // 统计频率
 5     TreeNode* pre = NULL;
 6     vector<int> result;
 7     void searchBST(TreeNode* cur) {
 8         if (cur == NULL) return ;
 9 
10         searchBST(cur->left);       // 左
11                                     // 中
12         if (pre == NULL) { // 第一个节点
13             count = 1;
14         } else if (pre->val == cur->val) { // 与前一个节点数值相同
15             count++;
16         } else { // 与前一个节点数值不同
17             count = 1;
18         }
19         pre = cur; // 更新上一个节点
20 
21         if (count == maxCount) { // 如果和最大值相同，放进result中
22             result.push_back(cur->val);
23         }
24 
25         if (count > maxCount) { // 如果计数大于最大值频率
26             maxCount = count;   // 更新最大频率
27             result.clear();     // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
28             result.push_back(cur->val);
29         }
30 
31         searchBST(cur->right);      // 右
32         return ;
33     }
34 
35 public:
36     vector<int> findMode(TreeNode* root) {
37         count = 0;
38         maxCount = 0;
39         TreeNode* pre = NULL; // 记录前一个节点
40         result.clear();
41 
42         searchBST(root);
43         return result;
44     }
45 };

236. 二叉树的最近公共祖先

 1 class Solution {
 2 public:
 3     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
 4         if (root == q || root == p || root == nullptr)   return root;
 5         TreeNode* left = lowestCommonAncestor(root->left, p ,q);
 6         TreeNode* right = lowestCommonAncestor(root->right, p, q);
 7         if (left != nullptr && right != nullptr) return root;
 8         if (left == nullptr && right != nullptr) return right;
 9         else if (left != nullptr && right == nullptr) return left;
10         else {
11             return nullptr;
12         }
13     }
14 };