530.二叉搜索树的最小绝对差
视频讲解：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;
}学习反思
递归的终止条件为：如果当前节点为空，或者当前节点为p，或者当前节点为q，说明已经找到其中一个节点，返回当前节点。然后递归查找左子树和右子树，分别得到左子树中的LCA节点和右子树中的LCA节点。根据以下三种情况判断当前节点是否为LCA：
- 如果在左子树和右子树中都找到了节点p和q，说明当前节点是LCA，直接返回当前节点。
- 如果只在左子树中找到了节点p和q，说明LCA在左子树中，返回左子树中的LCA节点。
- 如果只在右子树中找到了节点p和q，说明LCA在右子树中，返回右子树中的LCA节点。
最后，返回找到的LCA节点。时间复杂度为O(n)。
总结
加油！！！