@ 代码随想录算法训练营第4周(C语言)|Day21(二叉树)
Day21、二叉树(包含题目 ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先 )
530.二叉搜索树的最小绝对差
题目描述
给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。
题目解答
struct TreeNode*pre;
void absnode(struct TreeNode*root,int*result){
if(root==NULL){
return;
}
absnode(root->left,result);
if(pre!=NULL){
*result=(*result)>(root->val-pre->val)?(root->val-pre->val):(*result);
}
pre=root;
absnode(root->right,result);
}
int getMinimumDifference(struct TreeNode* root) {
int result=INT_MAX;
pre=NULL;
absnode(root,&result);
return result;
}
题目总结
搜索二叉树对应中序左中右。
501.二叉搜索树中的众数
题目描述
给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。
题目解答
int pre;
int count;
int maxcount;
int*res;
int resnum;
void dfs(struct TreeNode* root){
if(root==NULL){
return;
}
dfs(root->left);
if(pre==root->val){
count++;
}else{
count=1;
pre=root->val;
}
if(count==maxcount){
res[resnum++]=pre;
}
if(count>maxcount){
resnum=0;
res[resnum++]=pre;
maxcount=count;
}
dfs(root->right);
}
int* findMode(struct TreeNode* root, int* returnSize) {
int*res=(int*)malloc(sizeof(int)*4001);
pre=count=maxcount=resnum=0;
dfs(root);
*returnSize=resnum;
return res;
}
题目总结
各个参数有不同的意义。
236. 二叉树的最近公共祖先
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
题目解答
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
if(root==NULL){
return NULL;
}
//应该是或关系
if(root==p||root==q){
return root;
}
struct TreeNode*left=lowestCommonAncestor(root->left,p,q);
struct TreeNode*right=lowestCommonAncestor(root->right,p,q);
if(left!=NULL&&right!=NULL){
return root;
}
if(left!=NULL&&right==NULL){
return left;
}else if(right!=NULL&&left==NULL){
return right;
}else{
return NULL;
}
}
题目总结
后序遍历(左右中)就是天然的回溯过程,可以根据左右子树的返回值,来处理中节点的逻辑,后续回溯。