day21 二叉搜索树的最小绝对差 二叉搜索树中的众数 二叉搜索树的最近公共祖先

题目1：530 二叉搜索树的最小绝对差

题目链接：530 二叉搜索树的最小绝对差

题意

返回二叉搜索树的两个不同节点间的最小差值（是一个正数，取绝对值）

注意利用二叉搜索树的性质??中序遍历得到的是一个有序单调递增的数组

递归

递归三部曲：

1）递归函数的参数和返回值

2）终止条件

3）单层递归逻辑

数组

将二叉树中序遍历，得到一个有序的单调递增的数组，然后再遍历数组，求解相邻两个数之间的差值

代码

/**
 * 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> vec;
    void traversal(TreeNode* root){
        //终止条件
        if(root==NULL) return;
        //单层递归逻辑
        //中序遍历  左中右
        traversal(root->left);//左
        vec.push_back(root->val);//中
        traversal(root->right);//右
    }
    int getMinimumDifference(TreeNode* root) {
        int minvalue = INT_MAX;
        traversal(root);
        for(int i=0;i<vec.size();i++){
            if(i>=1 && vec[i]-vec[i-1]<minvalue){
                minvalue = vec[i] - vec[i-1];
            }
        }
        return minvalue;
    }
};

双指针（★）

使用一个指针pre指向当前遍历节点的前一个节点，将pre->val与root->val作差，并与当前的最小值比较

代码

/**
 * 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 minvalue = INT_MAX;
    TreeNode* pre = NULL;
    void traversal(TreeNode* root){
        //终止条件 
        if(root==NULL) return;
        //单层递归逻辑
        //中序遍历  左中右
        traversal(root->left);//左
        if(pre!=NULL) minvalue = min(minvalue,root->val-pre->val);//中
        pre = root;//一定要注意移动pre
        traversal(root->right);//右
    }
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return minvalue;
    }
};

题目2：501 二叉搜索树中的众数

题目链接：501 二叉搜索树中的众数

题意

本题的二叉搜索树中含有重复值，找出所有的众数（顺序不计）

节点的左子树中的节点值均小于等于该节点值 ；节点的右子树的节点值均大于等于该节点值

递归

递归三部曲：

1）递归函数的参数和返回值

2）终止条件

3）单层递归逻辑

普通二叉树（使用map计数）

不能直接对map中的value排序，需要将map转化为数组vector（vector是pair<int,int>类型的数），再进行排序

代码

/**
 * 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:
    unordered_map<int,int> map;
    void traversal(TreeNode* root){
        //终止条件
        if(root==NULL) return;
        //单层递归逻辑
        //中序遍历 左中右
        traversal(root->left);//左
        //中  使用map统计元素出现的频率
        map[root->val]++;
        //右
        traversal(root->right);
    }
    //将map中的value按照从大到小排序
    bool static cmp(const pair<int,int>& a,const pair<int,int>& b){
        return a.second > b.second;
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> result;
        traversal(root);
        //将map转化为vector进行排序
        vector<pair<int,int>> vec(map.begin(),map.end());
        sort(vec.begin(),vec.end(),cmp);
        //排在数组中第一位的元素一定是出现频率最大的元素
        result.push_back(vec[0].first);
        for(int i=1;i<vec.size();i++){
            if(vec[i].second == vec[0].second) result.push_back(vec[i].first);
        }
        return result;
    }
};

双指针（针对二叉搜索树）

中序遍历（左中右）

代码

/**
 * 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> result;//存放最终的众数集合
    int maxvalue = 0;//记录出现的最大次数
    int count = 0;//记录单个元素出现的次数
    TreeNode* pre = NULL;//pre指针指向当前遍历节点的前一个节点
    void traversal(TreeNode* root){
        //终止条件
        if(root==NULL) return;
        //单层递归逻辑
        //中序遍历 左中右
        traversal(root->left);//左
        //中
        //记录当前元素遍历的次数
        if(pre==NULL) count = 1;//遍历第一个元素时，pre还为NULL
        else if(pre!=NULL && pre->val==root->val) count++;//当前遍历节点的值与前一个节点的值相等
        else count = 1;//当前遍历节点的值与前一个节点的值不等
        pre = root;//移动pre
        //比较当前遍历节点出现的次数count与最大次数的关系
        if(count == maxvalue) result.push_back(root->val);
        else if(count > maxvalue){
            maxvalue = count;
            result.clear();//注意这里一定要清空数组，重新往里面放值
            result.push_back(root->val);
        }
        //右
        traversal(root->right);
    }
    vector<int> findMode(TreeNode* root) {
        traversal(root);
        return result;
    }
};

题目3：236 二叉树的最近公共祖先

题目链接：236 二叉树的最近公共祖先

题意

找出二叉数中两个指定节点的最近公共祖先（深度尽可能大），一个节点的也可是它自己的祖先

二叉树中的值均不同，且这两个指定节点均存在给定二叉树中，且这两个指定的节点不同

递归

递归三部曲：

1）递归函数的参数和返回值

2）终止条件

3）单层递归逻辑

使用后序遍历? 根据节点的左右孩子的情况，处理该节点

节点的左子树出现了p或q，就向上返回，返回值不为空，节点的右子树出现了q或p，就向上返回，返回值也不为空，那么该节点就是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) return NULL;
        if(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;
    }
};