过外婆八十寿宴，补卡
二叉搜索树的最小绝对差
leetcode：530. 二叉搜索树的最小绝对差
双指针中序遍历法
思路
搜索树的最小绝对差一定出现在中序遍历的相邻两个元素之间。
设置前后两个指针，每次对比“历史最小”与当前node->val - pre->val的值哪个更小，进行相应更新。
复杂度分析
时间复杂度：O(N)。遍历一遍。
空间复杂度：递归栈深度，树的深度。近完全时O(logN)，近链表时O(N)。
注意点
pre = node是一定要执行的，不要写到else里了
代码实现
/**
* 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:
TreeNode* pre;
int result = INT32_MAX;
void traversal(TreeNode* node){
// 空节点结束
if(node == NULL) return;
// 中序遍历
traversal(node->left);
if(pre) result = min(result,node->val - pre->val);
pre = node; // 这句一定要执行，不要写到else里了
traversal(node->right);
}
int getMinimumDifference(TreeNode* root) {
traversal(root);
return result;
}
};
二叉搜索树中的众数
leetcode：501. 二叉搜索树中的众数
递归遍历通法
思路
遍历整棵树，建立map映射，value最大的为众数。
复杂度分析
时间复杂度：O(N)。但是三个并列的O(N)级别。
空间复杂度：递归栈深度，最好O(logN)，最差O(N)。
注意点
- map的元素类型是pair<T,T>。
代码实现
/**
* 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:
// 中序遍历，map映射
unordered_map<int,int> map;
void traversal(TreeNode* node){
// 空节点终止
if(node == NULL) return;
traversal(node->left);
map[node->val]++;
traversal(node->right);
}
vector<int> findMode(TreeNode* root) {
traversal(root);
// 找最大频数
int mostFreq = 0;
for(pair<int,int> p : map){
mostFreq = max(mostFreq,p.second);
}
// 根据最大频数找众数
vector<int> vec;
for(pair<int,int> p : map){
if(p.second == mostFreq) vec.push_back(p.first);
}
return vec;
}
};
Carl的做法是把map转化为vector，然后再排序、取首或末的那些元素（取决于排序规则）。
搜索树中序遍历法
思路
搜索树，中序遍历下众数一定是连续出现的，只需要一个count变量计数即可。
复杂度分析
时间复杂度：O(N)。遍历一遍。
空间复杂度：递归栈深度，最好O(logN)，最差O(N)。
注意点
-
count、maxCount要初始化为1，否则第一个节点会无法正常置入result。
（因为在第二个节点时，若前后节点不等，count会置为1而maxCount默认值为0，再往下会
count > maxCount，清空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:
// 一次中序遍历
// 注意这两个变量都必须初始化为1
int count = 1;
int maxCount = 1;
TreeNode* pre;
vector<int> result;
void traversal(TreeNode* cur){
// 终止条件是空节点
if(cur == NULL) return;
// 中序遍历
traversal(cur->left);
// 中
// 根据值处理count
if(pre){
if(pre->val == cur->val) count++; // 和前一个值相等，count++
else count = 1; // 值不等时归1
}
// 根据count找众数
if(count >= maxCount){ // count>=maxCount的时候都放入结果数组
// 如果count>maxCount就更新maxCount和result数组（清空）
if(count > maxCount){
maxCount = count;
result.clear();
}
result.push_back(cur->val);
}
pre = cur; // 前指针后移
// 右
traversal(cur->right);
}
vector<int> findMode(TreeNode* root) {
traversal(root);
return result;
}
};
二叉树的最近公共祖先
leetcode：236. 二叉树的最近公共祖先
思路
node->val互异且p、q都存在。
要找公共祖先需要自底向上遍历，因此选择后序遍历，在向上回溯过程中进行操作。
- 如果是p、q，则直接向上返回当前节点（涵盖了第二种情况）；是空节点也返回当前节点（NULL）。
- 设立两个节点接收左、右递归结果。都空表示没有找到p、q，返回NULL；一侧非空表示找到了p或q，返回非空的那个节点；如果都不空则说明p、q都找到了，当前节点就是最近公共祖先，返回。
复杂度分析
时间复杂度：O(N)。
空间复杂度：递归栈深度，树的高度。树近完全时候O(logN)，倾斜时O(N)。
注意点
略
代码实现
/**
* 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) {
// 为空时返回NULL；为p或q时返回自身
if(!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
if(!left && !right) return NULL; // 左右都为空，向上也返回空
else if(!left && right) return right; // 左空右不空，向上返回右
else if(left && !right) return left; // 左不空右空，向上返回左
else return root; // 左右都不空，root就是公共祖先，返回
}
};