难度:Easy
给定一个二叉树,计算整个树的坡度。
一个树的节点的坡度定义即为,该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。
示例:输入:1/ \2 3输出: 1解释:结点的坡度 2 : 0结点的坡度 3 : 0结点的坡度 1 : |2-3| = 1树的坡度 : 0 + 0 + 1 = 1注意:任何子树的结点的和不会超过32位整数的范围。坡度的值不会超过32位整数的范围。
使用递归,需要一个辅助函数计算所有节点和,一个全局变量计算所有坡度和。
/*** 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 {private:int res=0;int getSum(TreeNode* root){if(!root) return 0;int left, right;left=getSum(root->left);right=getSum(root->right);res+=abs(left - right);return left+right+root->val ;}public:int findTilt(TreeNode* root) {getSum(root);return res;}};
执行用时 :40ms, 在所有 C++ 提交中击败了65.67%的用户 内存消耗 :21.5MB, 在所有 C++ 提交中击败了99.47%的用户