563. Binary Tree Tilt

xiaoxiao2021-02-28  12

563. Binary Tree Tilt       

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.

        这道题是说对于二叉树的每一个节点,分别求其左右子树和sL,sR,再求其差的绝对值的和,即:Σ|sL-sR|。

     思路也比较直接,就是递归每个节点,求解即可。

class Solution { public: int sumOfsubtree(TreeNode* r) { if (r == NULL) return 0; return r->val + sumOfsubtree(r->left) + sumOfsubtree(r->right); } int findTilt(TreeNode* root) { if (root == NULL) return 0; return abs(sumOfsubtree(root->left) - sumOfsubtree(root->right))+findTilt(root->left)+findTilt(root->right); } };   

转载请注明原文地址: https://www.6miu.com/read-450043.html

最新回复(0)