day21
530.二叉搜索树的最小绝对差
题目链接：530. 二叉搜索树的最小绝对差
解题思路：解题参考
1.将二叉搜索树按照中序遍历方法保存到一个数组中，数组一定为单调递增数组，比较数组中相邻两个节点之间的值，返回结果即可
2.双指针法
/**
* 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:
// 定义全局变量
vector<int> vec;
// 1.确定递归函数的返回值和参数
void traversal(TreeNode* node){
// 2.确定终止条件
if( node == NULL ) return;
// 3.确定单层递归逻辑
// 左
traversal( node->left );
// 中
vec.push_back( node->val );
// 右
traversal( node->right );
}
int getMinimumDifference(TreeNode* root) {
traversal( root );
int result = INT_MAX;
for ( int i = 1; i < vec.size(); i++){
if ( abs(vec[i]-vec[i-1]) < result ){
result = abs(vec[i]-vec[i-1]);
}
}
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 {
public:
int result = INT_MAX;
TreeNode* pre = NULL;
// 1.确定返回值和参数
void traversal( TreeNode* node){
// 2.确定终止条件
if ( node == NULL ) return;
// 确定单层递归逻辑
// 左
traversal( node->left );
// 中
if ( pre != NULL ) result = min(result,node->val - pre->val);
pre = node; //给pre指针赋值
//右
traversal( node->right );
// return result;
}
int getMinimumDifference(TreeNode* root) {
traversal(root);
return result;
}
};
501.二叉搜索树中的众数
题目链接：501. 二叉搜索树中的众数
解题思路：双指针法，通过定义两个指针，采用中序遍历逻辑，主要在于中序遍历的中逻辑处理过程，当pre为空时候，当pre的value和cur的value相等的时候，处理。然后执行pre=cur操作。之后注意代码的技巧，如果找到众数更新MaxCount。
/**
* 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 = NULL; // pre指针
int count = 0; // 计数
int MaxCount = 0; // 最大数量
vector<int> result; // 结果数组
// 1.确定递归函数的返回值和参数
void traversal( TreeNode* cur ){
// 2.确定终止条件
if ( cur == NULL ) return;
// 3.单层递归逻辑
traversal( cur->left ); //左
// 中
if ( pre == NULL ) count = 1; //计数初始化 第一个节点
else if( pre->val == cur->val ) count++; //如果两个指针的值相等计数加1
else{
count = 1;
}
pre = cur;
if( count == MaxCount ) result.push_back( cur->val );
else if( count > MaxCount ){
MaxCount = count; //更新最大频率
result.clear(); //清空result
result.push_back( cur->val);
}
traversal( cur->right );
return ;
}
vector<int> findMode(TreeNode* root) {
traversal( root );
return result;
}
};
236.二叉树的最近公共祖先
题目链接：236. 二叉树的最近公共祖先
解题思路：后续遍历递归，自底向上，有回溯在里面
使用递归三部曲，首先确定递归函数的返回值和参数，返回值为二叉树的节点TreeNode*类型，参数三个，一个根节点，一个p，一个q；然后确定终止条件，当节点为空或者等于q或者p的时候，返回这个节点
然后按照后续遍历的步骤，左右中开始写
中就是为了得到结果，所以用四个判断来写，分别判断得到不同情况时候的返回值，注意一直从下向上返回。
下面是总体的代码实现
/**
* 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:
// 1.确定递归函数的返回值和参数
TreeNode* traversal(TreeNode* node, TreeNode* p, TreeNode* q){
// 2.确定终止条件
if( node == NULL ) return node;
if( node == p || node == q) return node;
// 3.确定单层递归逻辑 后序遍历
// 左
TreeNode* left = traversal( node->left, p, q);
// 右
TreeNode* right = traversal( node->right, p, q);
// 中 判断左右是否为空
if( left != NULL && right != NULL ) return node; //左右不为空都向上返回root
else if( left != NULL && right == NULL ) return left; //
else if( left == NULL && right!= NULL ) return right;
else{ return NULL; }
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return traversal( root,p,q);
}
};