题目描述

假设，每个二叉树的结点都存储了一个值
1. 每个子树的所有结点之和称为这个子二叉树的权重。
2. 每个结点的左右子树的权重差的绝对值为$|左子树的权重 - 右子树的权重|$
写程序，计算整个二叉树的最大权重差
注：好像是哪一年阿里的面试题

/**
 * 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 res = 0;   // 最大权重差
    int GetMaxGap(TreeNode* root) {
        dfs(root);
        return res;
    }

    int dfs(TreeNode* root)
    {
        // 递归处理左右子树，返回各自的二叉树的值
        int ans = 0;   // 当前树的二叉树值
        if (!root)  return 0;    // 给后面省点代码
        if (!root->left && !root->right)  return root->val;   // 递归到叶节点
        int l = dfs(root->right);
        int r = dfs(root->left);
        res = max(res, abs(l - r));
        ans += l + r;
        return ans;
    }
};