文章
15
粉丝
0
获赞
1
访问
3.5k
1.利用中序遍历的思想,定义全局变量count,建立一个数组,分别记录各个结点的前驱和后继,统计两者与本结点的最小距离,若相等则将count加一,继续遍历直到完成,返回count
2.
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int counts = 0;
void MTraverse(TreeNode *T,int M[],int i){
if(T==NULL){return ;}
else {
MTraverse(T->left,M,i-1);
M[i] = T->val;
//遍历数组找到比i小的元素中最大的值
int max = 0;
for (int j = 0; j < i; ++j) {
if(M[j]>max){
max = M[j];
}
}
//找到比i大的元素中最大值
int min = 0x7FFFFFFF;//C语言中的最大值
for (int j = i+1; j < n; ++j) {
if(M[j]<min){
min = M[j];
}
}
if(M[i]-max==min-M[i] && T->right!=NULL&&T->left!=NULL){
counts++;
}
MTraverse(T->right,M,i+1);
}
}
3.时间复杂度O(nlogn),空间复杂度O(n)
int funcs(TreeNode *T){
//统计T中count的个数
...
登录后发布评论
暂无评论,来抢沙发