目录
? ? ? ? 本题要求在二叉搜索树上任意两节点的差的绝对值的最小值。与上题验证二叉搜索树题目类似，可以用数组保存二叉树节点数值进行操作的直接法，也可以利用双指针法进行实现。
/**
* 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 {
private:
vector<int> vec;
void traversal(TreeNode* node){
if (node == NULL) return;
traversal(node->left);
vec.push_back(node->val);
traversal(node->right);
}
public:
int getMinimumDifference(TreeNode* root) {
vec.clear();
traversal(root);
int result = INT_MAX;
for (int i = 0; i < vec.size() - 1; i++){
result = min(result, vec[i + 1] - vec[i]);
}
return 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 {
private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* node){
if (node == NULL) return;
traversal(node->left); //左
if (pre != NULL){ //中
result = min(result, node->val - pre->val);
}
pre = node;
traversal(node->right);//右
}
public:
int getMinimumDifference(TreeNode* root) {
traversal(root);
return 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 {
private:
void searchBST(TreeNode* cur, unordered_map<int, int>& map){
if (cur == NULL) return;
map[cur->val]++; //统计元素频率
searchBST(cur->left, map);
searchBST(cur->right, map);
return;
}
//自定义排序函数
bool static cmp (const pair<int, int>& a, const pair<int, int>& b){
return a.second > b.second;
}
public:
vector<int> findMode(TreeNode* root) {
unordered_map<int, int> map;
vector<int>result;
if (root == NULL) return result;
searchBST(root, map);
vector<pair<int, int>> vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), cmp); //给频率排序
result.push_back(vec[0].first);
for (int i = 1; i < vec.size(); i++){
if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
else break; //vec已按频率排序，若下一个未出现频率相同元素就没有了
}
return result;
}
};? ? ? ? 主要是创建映射map记录递归过程中每个节点值及该值出现的次数。然后在主函数中对map中保存的value（即每个数的出现频率）进行排序，在该过程中创建了自定义比较函数cmp对sort中的元素进行降序排序。将排序最高的元素对应的key值保存入result数组数组中，再进行循环判断是否有和当前最大频率相等的数值，有则继续将对应的key值保存入result，由于vec已按频率排序，若下一个未出现频率相同元素就没有了，最终返回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 {
private:
int MaxCount = 0;
int count = 0;
TreeNode* pre = NULL;
vector<int> result;
void searchBST(TreeNode* cur){
if (cur == NULL) return;
//左
searchBST(cur->left);
//中
if (pre == NULL){ //第一个节点
count = 1;
}
else if (cur->val == pre->val){ //与前一个数值相同
count++;
}
else{ //与前一个数值不同
count = 1;
}
pre = cur; //更新pre
if (MaxCount == count) { //和最大值相同，存放入result数组中
result.push_back(cur->val);
}
if (MaxCount < count){ //计数大于当前最大计数
MaxCount = count; //更新最大计数
result.clear(); //清空result
result.push_back(cur->val);
}
//右
searchBST(cur->right);
return;
}
public:
vector<int> findMode(TreeNode* root) {
count = 0;
MaxCount = 0;
pre = NULL;
result.clear();
searchBST(root);
return result;
}
};? ? ? ? 本算法的巧妙之处在于只需遍历一次二叉树就可以搜索到所有众数，难点在于如何在一次遍历过程就能确定最大频率。
? ? ? ? 查找二叉树两节点的最近公共祖先，可以利用后序递归的回溯过程，子弟向上查找最近的公共祖先，根据左右子树的返回值，来处理中节点的逻辑。
? ? ? ? 要判断哪个数是两个节点的最近公共祖先，首先最容易想到的一个情况：如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先，还有一个情况是节点本身是公共祖先。
/**
* 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) {
if (root == q || root == p || root == NULL) return root;
//遍历整棵二叉树要有有变量作为返回值
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL && right != NULL) return root;
if (left == NULL && right != NULL) return right;
else if (left != NULL && right == NULL) return left;
else {
return NULL;
}
}
};? ? ? ? 算法实现比较简单，但思路却更加重要，情况二是包含在了情况一的算法实现过程中。
? ? ? ? 二叉树遍历处理过程中的一些技巧和思路需要多做题总结，实现上确实巧妙。