即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

LeetCode 563. Binary Tree Tilt

编程语言 sinat_36053757 145℃ 0评论

题目:


Given a binary tree, return the tilt of the whole tree.

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.

The tilt of the whole tree is defined as the sum of all nodes’ tilt.

Example:

Input: 
         1
       /   \
      2     3
Output: 1
Explanation: 
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1

Note:

The sum of node values in any subtree won’t exceed the range of 32-bit integer.


All the tilt values won’t exceed the range of 32-bit integer.

思路:


见注释

代码:

/**
 * 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 findTilt(TreeNode* root) {
        help(root);//借用help函数来进行递归调用,因为返回值和findTilt不一样
        return tilt;
    }
private:
    int tilt=0;    //tilt为结果,初始化为0
    int help(TreeNode* root){
        if(root==NULL){//如果根节点为NULL,直接返回0
            return 0;
        }
        int left=help(root->left);//递归计算左子节点的和
        int right=help(root->right);//递归计算右子节点的和
        tilt+=abs(left-right);//计算当前节点的tilt值
        return root->val+left+right;
    }
};

输出结果: 16ms

转载请注明:CodingBlog » LeetCode 563. Binary Tree Tilt

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情