Leetcode 563 : 二叉树的坡度
问题：
思路：
分治递归
递归函数有两个作用，一是计算树的节点和（也是递归函数的返回值），树的节点和=根节点值+左子树节点和+右子树节点和。定义全局变量记录节点坡度和，在递归函数计算完左子树节点和以及右子树节点和后，计算根节点的坡度，然后全局变量加上该根节点的坡度完成更新。递归结束后，全局变量的值即为所有节点坡度之和。
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int sum_and_tilt( TreeNode* p,int &tilt )
{
if( p==NULL )
return 0;
int leftsum;
int rightsum;
leftsum=sum_and_tilt( p->left,tilt );
rightsum=sum_and_tilt( p->right,tilt );
tilt+=abs( leftsum-rightsum );
return p->val+leftsum+rightsum;
}
int findTilt(TreeNode* root) {
int tilt=0;
sum_and_tilt( root,tilt );
return tilt;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153865.html
