文章
15
粉丝
0
获赞
1
访问
2.7k
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的个数 ...
登录后发布评论
暂无评论,来抢沙发