代码随想录算法训练营第二十一天|530.二叉搜索树的最小绝对差、 501.二叉搜索树中的众数、236. 二叉树的最近公共祖先

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

题目链接/文章讲解：代码随想录

视频讲解：二叉搜索树中，需要掌握如何双指针遍历！| LeetCode：530.二叉搜索树的最小绝对差_哔哩哔哩_bilibili

1.方法1

1.1分析及思路

了解到差值最小的数为，结点左孩子然后一直向右的叶子结点，或者是右孩子一直向左的叶子结点。

对每一个结点都进行这样的判断。所以就用到了递归。

递归三部曲：

1.功能，参数，返回值

功能：判断结点的最小差值

参数：保存最小值的int*地址，以及结点

返回值：没有必要向上层返回值，所以不需要返回值

2.递归终止条件

假设传入一个非空结点，要进行的操作就是，寻找其前后最接近的值。所以只有NULL是才会结束循环。

3.单层递归逻辑

拿到一个结点，要进行寻找其左孩子的最右结点，以及右孩子的最左结点，然后求最小差值。

1.2代码及注释

void LETF(struct TreeNode* root,int* Min) {
    // 定义一个指向左子树的节点Node
    struct TreeNode* Node = root->left;
    // 遍历左子树
    while(Node!=NULL){
        // 如果Node的右子节点为空，则说明找到了，左孩子的最右侧的叶子结点
        if(Node->right == NULL)
            // 更新最小值Min
            if(*Min > root->val - Node->val)
                *Min = root->val - Node->val;
        Node = Node->right;
    }
}

void RIGHT(struct TreeNode* root,int* Min) {
    // 定义一个指向右子树的节点Node
    struct TreeNode* Node = root->right;
    // 遍历右子树
    while(Node!=NULL){
        // 如果Node的左子节点为空，则说明找到了右孩子的最左侧叶子结点
        if(Node->left == NULL)
            // 更新最小值Min
            if(*Min > Node->val - root->val)
                *Min = Node->val - root->val;
        Node = Node->left;
    }
}

void traversal(struct TreeNode* root,int* Min) {
    // 如果当前节点为空，直接返回
    if(root == NULL) return;
    if(root->left != NULL)
        LETF(root,Min);//寻找左孩子的最右侧叶子结点
    if(root->right != NULL)
        RIGHT(root,Min);//寻找右孩子的最左侧结点
    // 递归遍历左子树
    traversal(root->left,Min);
    // 递归遍历右子树
    traversal(root->right,Min);
}

int getMinimumDifference(struct TreeNode* root) {
    // 初始化最小值为INT_MAX
    int Min = INT_MAX;
    // 从根节点开始遍历
    traversal(root,&Min);
    // 返回最小值
    return Min;
}

2.方法2

2.1分析及思路

与98.验证二叉搜索树思路类似，用两个指针进行遍历，这俩个指针的差值是可能成为最小差值的，因为中序遍历是会得到一个递增的数组的。

1.功能、参数、返回值

功能：得到最小的差值

参数：保存最小差值的Min、根节点root、访问过的前一个结点pre

返回值：下一侧递归不需要及时返回信息，所以不需要返回值

2.终止条件

当访问到NULL时说明该树已经访问完毕。所以终止条件为NULL

3.单层递归的逻辑

拿到一个结点root，用root-pre判断差值，然后递归的访问其左子树，右子树

2.2代码及分析

// 定义一个函数用于遍历二叉搜索树
void traversal(struct TreeNode* root, struct TreeNode* *pre, int* Min) {
    // 如果当前节点为空，直接返回
    if(root == NULL) return;
    
    // 递归遍历左子树
    traversal(root->left, pre, Min);
    
    // 如果前一个节点不为空
    if(*pre != NULL){
        // 更新最小差值
        if(*Min > (root->val - (*pre)->val)){
            *Min = (root->val - (*pre)->val);
        }
    }
    
    // 更新前一个节点为当前节点
    *pre = root;
    
    // 递归遍历右子树
    traversal(root->right, pre, Min);
}

// 定义一个函数用于获取二叉搜索树中节点值的最小差值
int getMinimumDifference(struct TreeNode* root) {
    // 初始化最小差值为最大整数值
    int Min = INT_MAX;
    
    // 初始化前一个节点为空
    struct TreeNode* pre = NULL;
    
    // 调用遍历函数
    traversal(root, &pre, &Min);
    
    // 返回最小差值
    return Min;
}

501.二叉搜索树中的众数

代码随想录

视频讲解：不仅双指针，还有代码技巧可以惊艳到你！ | LeetCode：501.二叉搜索树中的众数_哔哩哔哩_bilibili

1.分析及思路

最直观的想法就是，访问一遍树，把所有的数出现的频率都统计下来，然后再把频率高的数进行返回。

进行优化，对于二叉搜索树而言，中序遍历会得到一个不减的数组，和上一题类似，使用双指针进行频率的统计，如果当前频率等于最大频率，则说明众数有多个，在结果数组的末尾加上它即可。若大于则说明，已经统计的结果全部作废，要重新统计，即再次从数组下标为0的地方存储结果。

运用了中序遍历，所以可以使用递归法，递归三部曲：

1.功能，参数，返回值

功能：统计二叉树中的众数

参数：需要传入一个根节点，所以有struct TreeNode* root

因为是双指针，所以需要一个struct TreeNode** pre，保存上次访问过的结点

最终返回的是一个数组，所以穿进来一个int* result

以及统计数组的大小的int* returnSize

需要当前频率和最大频率做对比，所以有int* MaxCount,int* NowCount。

2.递归终止条件

很明显，遇到空结点时，没办法统计所以终止。

3.单层递归逻辑

遇到一个结点，看上次访问的结点与它是否相等，相等则频率加1。若不想等则说明，此时访问的是新出现的，此时频率设置为1。若该频率与最大频率相等，则把它加入结果数组的末尾。若大于，则说明，结果数组中的众数全部作废，重新统计。

2.代码及注释

void traversal(struct TreeNode* root, struct TreeNode** pre, int* returnSize, int* result, int* MaxCount, int* NowCount) {
    // 如果当前节点为空，直接返回
    if(root == NULL) return;
    
    // 递归遍历左子树
    traversal(root->left, pre, returnSize, result, MaxCount, NowCount);
    
    // 如果前一个节点为空，则当前节点是第一个节点，NowCount置为1
    if(*pre == NULL) *NowCount = 1;
    // 如果前一个节点的值等于当前节点的值，则当前节点是重复节点，NowCount加1
    else if((*pre)->val == root->val) (*NowCount)++;
    // 如果前一个节点的值不等于当前节点的值，则当前节点是新节点，NowCount置为1
    else *NowCount = 1;
    
    // 更新pre指针为当前节点
    *pre = root;
    
    // 如果NowCount等于MaxCount，将当前节点的值加入结果数组并增加返回大小
    if(*NowCount == *MaxCount) result[(*returnSize)++] = root->val;
    // 如果NowCount大于MaxCount，更新MaxCount为NowCount，重置返回大小为1，将当前节点的值放入结果数组
    else if(*NowCount > *MaxCount){
        *MaxCount = *NowCount;
        *returnSize = 1;
        result[0] = root->val;
    }
    
    // 递归遍历右子树
    traversal(root->right, pre, returnSize, result, MaxCount, NowCount);
}

int* findMode(struct TreeNode* root, int* returnSize) {
    // 初始化返回大小为0
    *returnSize = 0;
    
    // 分配结果数组的内存空间
    int* result = (int*)malloc(sizeof(int)*10001);
    
    // 初始化前一个节点指针、最大出现次数、当前出现次数为0
    struct TreeNode* pre = NULL;
    int MaxCount = 0;
    int NowCount = 0;
    
    // 调用traversal函数进行遍历
    traversal(root, &pre, returnSize, result, &MaxCount, &NowCount);
    
    // 返回结果数组
    return result;
}

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

代码随想录

视频讲解：自底向上查找，有点难度！ | LeetCode：236. 二叉树的最近公共祖先_哔哩哔哩_bilibili

1.分析及思路

很明显，要想知道最近公共祖先结点，就要从该结点左右子树中找到qp两个结点。也就是先访问其左子树，再访问其右子树，也就是使用的是后续遍历。即找到结点后就向父结点返回。

递归三部曲：

1.功能、参数、返回值

功能：返回最近公共祖先

参数：根节点、p、q

返回值：因为需要向父结点返回有没有该结点，所以需要返回值

2.递归终止条件

当传入NULL时，很明显终止。当找到该结点时，也应该终止。

3.单层递归逻辑

遇到结点时，先访问其左子树，在访问其右子树，才能得到该结点是不是有，目标结点。

1.若左子树有目标结点，右子树也有目标结点，则说明它就是最近公共祖先。

2.若右子树有，左子树没有，则说明最近公共祖先在右侧，即返回右侧返回的结点

3.左子树有，右子树没有，则返回左子树返回的值

4.若都没有很明显，返回NULL

2.代码及注释

// 定义一个函数，用于找到两个节点的最近公共祖先
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    // 如果根节点为空，返回空
    if(root == NULL) return root;
    // 如果根节点等于其中一个节点，直接返回根节点
    if(root == q || root == p) return root;
    // 递归查找左子树中的最近公共祖先
    struct TreeNode* left = lowestCommonAncestor(root->left,p,q);
    // 递归查找右子树中的最近公共祖先
    struct TreeNode* right = lowestCommonAncestor(root->right,p,q);
    // 如果左右子树都找到了最近公共祖先，则返回根节点
    if(left != NULL && right != NULL) return root;
    // 如果左子树找到了最近公共祖先，则返回左子树的最近公共祖先
    if(left == NULL && right != NULL) return right;
    // 如果右子树找到了最近公共祖先，则返回右子树的最近公共祖先
    if(left != NULL && right == NULL) return left;
    // 如果左右子树都没有找到最近公共祖先，则返回空
    return NULL;
}