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

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

news 2025/6/6 19:30:30

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;
}