@ 代码随想录算法训练营第4周（C语言）|Day21（二叉树）

@ 代码随想录算法训练营第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;}
}

题目总结

后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑，后续回溯。