563. 二叉樹的坡度

給定一個(gè)二叉樹，計(jì)算 **整個(gè)樹 **的坡度 。

一個(gè)樹的** 節(jié)點(diǎn)的坡度 **定義即為，該節(jié)點(diǎn)左子樹的節(jié)點(diǎn)之和和右子樹節(jié)點(diǎn)之和的 **差的絕對(duì)值 **。如果沒(méi)有左子樹的話，左子樹的節(jié)點(diǎn)之和為 0 ；沒(méi)有右子樹的話也是一樣?？战Y(jié)點(diǎn)的坡度是 0 。

整個(gè)樹 的坡度就是其所有節(jié)點(diǎn)的坡度之和。

示例 1：

image

輸入：root = [1,2,3]
輸出：1
解釋：
節(jié)點(diǎn) 2 的坡度：|0-0| = 0（沒(méi)有子節(jié)點(diǎn)）
節(jié)點(diǎn) 3 的坡度：|0-0| = 0（沒(méi)有子節(jié)點(diǎn)）
節(jié)點(diǎn) 1 的坡度：|2-3| = 1（左子樹就是左子節(jié)點(diǎn)，所以和是 2 ；右子樹就是右子節(jié)點(diǎn)，所以和是 3 ）
坡度總和：0 + 0 + 1 = 1

示例 2：

image

輸入：root = [4,2,9,3,5,null,7]
輸出：15
解釋：
節(jié)點(diǎn) 3 的坡度：|0-0| = 0（沒(méi)有子節(jié)點(diǎn)）
節(jié)點(diǎn) 5 的坡度：|0-0| = 0（沒(méi)有子節(jié)點(diǎn)）
節(jié)點(diǎn) 7 的坡度：|0-0| = 0（沒(méi)有子節(jié)點(diǎn)）
節(jié)點(diǎn) 2 的坡度：|3-5| = 2（左子樹就是左子節(jié)點(diǎn)，所以和是 3 ；右子樹就是右子節(jié)點(diǎn)，所以和是 5 ）
節(jié)點(diǎn) 9 的坡度：|0-7| = 7（沒(méi)有左子樹，所以和是 0 ；右子樹正好是右子節(jié)點(diǎn)，所以和是 7 ）
節(jié)點(diǎn) 4 的坡度：|(3+5+2)-(9+7)| = |10-16| = 6（左子樹值為 3、5 和 2 ，和是 10 ；右子樹值為 9 和 7 ，和是 16 ）
坡度總和：0 + 0 + 0 + 2 + 7 + 6 = 15

示例 3：

image

輸入：root = [21,7,14,1,1,2,2,3,3]
輸出：9

提示：

• 樹中節(jié)點(diǎn)數(shù)目的范圍在 [0, 10<sup>4</sup>] 內(nèi)
• -1000 <= Node.val <= 1000

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int findTilt(TreeNode* root) {
        int count = 0;
        sum(root, count);
        return count;
    }

    int sum(TreeNode* node , int& count) {
        if(node == nullptr) return 0;
        int leftV = sum(node->left, count);
        int rightV = sum(node->right, count);
        count += abs(leftV - rightV);
        return leftV + rightV + node->val;
    }
};