当前位置：首页 > article >正文

代码随想录算法训练营第十七天|Day17二叉树

article 2024/10/23 13:28:43

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

题目链接/文章讲解： https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html

视频讲解：https://www.bilibili.com/video/BV1DD4y11779

思路

void inorder(struct TreeNode* root, int* prev, int* minDiff) {
    if (root == NULL) {
        return;
    }
    inorder(root->left, prev, minDiff);
    if (*prev != -1) { /
        int diff = root->val - *prev;
        if (diff < *minDiff) {
            *minDiff = diff; 
        }
    }
    *prev = root->val; 
    inorder(root->right, prev, minDiff);
}
int getMinimumDifference(struct TreeNode* root) {
    int minDiff = INT_MAX; 
    int prev = -1;   
    inorder(root, &prev, &minDiff); 
    return minDiff; 
}

学习反思

先遍历左子树，再处理当前节点，最后再遍历右子树。这样能够保证在遍历的过程中，按照升序来处理节点，从而能够计算出两个相邻节点的最小差值。在中序遍历的过程中，我们每次都更新上一个节点的值，然后计算当前节点和上一个节点值的差，并将其与最小差值进行比较，如果小于最小差值，则更新最小差值。最后返回最小差值即可。时间复杂度为O(n).

501.二叉搜索树中的众数

https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html题目链接/文章讲解：https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html

视频讲解：https://www.bilibili.com/video/BV1fD4y117gp

思路

int *modes;
int modesSize = 0;
int maxCount = 0;
int currentCount = 0;
int currentValue = 0;
void inorder(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    if (root->val == currentValue) {
        currentCount++; 
    } else {
        currentValue = root->val; 
        currentCount = 1; 
    }
    if (currentCount > maxCount) {
        maxCount = currentCount; 
        modesSize = 1; 
        modes = realloc(modes, sizeof(int) * modesSize); 
        modes[0] = currentValue; 
    } else if (currentCount == maxCount) {
        modes = realloc(modes, sizeof(int) * (modesSize + 1)); 
        modes[modesSize++] = currentValue;
    }
    inorder(root->right);
}
int* findMode(struct TreeNode* root, int* returnSize) {
    modes = NULL;  
    currentValue = 0; 
    currentCount = 0; 
    maxCount = 0;     
    modesSize = 0;    
    inorder(root); 
    *returnSize = modesSize; 
    return modes; 
}

学习反思

在中序遍历过程中，使用一个辅助结构来存储众数的列表和计数。每次遍历到一个节点，先判断当前值与之前的值是否相同，如果相同则增加计数，否则更新当前值和计数。然后比较当前计数与最大计数，如果当前计数大于最大计数，则更新最大计数，并重置众数列表为只包含当前值，否则如果当前计数等于最大计数，则将当前值添加到众数列表中。最后，返回众数列表和众数个数。时间复杂度为O(n)。

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

题目链接/文章讲解：

https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html

视频讲解：https://www.bilibili.com/video/BV1jd4y1B7E2

思路

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL || root == p || root == q) {
        return root;
    }
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) {
        return root;
    }
    return left ? left : right;
}