lesson16-3 二叉树每个节点坡度为左右子树和差绝对值 空节点为0
发布时间
阅读量：
阅读量
题目描述：
给定一棵二叉树，要求计算整棵树的坡度。
所谓树中某个节点的坡度，指的是该节点左子树所有节点数值之和与右子树所有节点数值之和之间的差值的绝对值。对于不存在的节点，其坡度默认为0。
整棵树的坡度等于所有节点坡度的总和。
思路：
需要分别计算每个节点及其左右子树的所有节点数值之和，采用后序遍历的方式进行处理，并在过程中同步计算各节点的坡度。
代码：
int getIncline(BTNode *t){
if(!t)
return 0;
int sum=0;
calcTilt(t,&sum);
return sum;
}
int calcTilt(BTNode *t,int *sum){
if(t==NULL)
return 0;
int left=calcTilt(t->lchild,sum);
int right=calcTilt(t->rchild,sum);
*sum+=ABS(left,right);//已定义的宏命令，计算两个数的绝对值
return t->data+left+right;//这一步只是返回给前面的结点，来计算对应全部评论 (0)
还没有任何评论哟~