563. Binary Tree Tilt

方法1: recursion

class Solution {
public:
    int findTilt(TreeNode* root) {
        int result = 0;
        if (!root) return result;
        unordered_map<TreeNode*, int> sum;
        
        int tilt = abs(getSum(root -> left, sum) - getSum(root -> right, sum));
        int leftTilt = findTilt(root -> left);
        int rightTilt = findTilt(root -> right);
        
        return tilt + leftTilt + rightTilt;      
    }
    
    int getSum(TreeNode* root, unordered_map<TreeNode*, int>& sum){
        if (sum.count(root)) return sum[root];
        if (!root) return 0;
        
        sum[root] = root -> val + getSum(root -> left, sum) + getSum(root -> right, sum);
        return sum[root];
    }  
};

方法2: postorder-traversal

思路：
由下而上计算子树中的sum，继续往上传，而子树的tilt则作为reference被一路累计。这两个值都应该由postorder来计算，但是方法不一样：sum更适合return，因为参与父节点sum的计算，tilt则除了累计对父节点没什么其他作用。

class Solution {
public:
    int findTilt(TreeNode* root) {
        int result = 0;
        if (!root) return 0;
        result += abs(postorderSum(root -> left, result) - postorderSum(root -> right, result));
        return result;
    }
    
    int postorderSum(TreeNode* root, int & result){
        if (!root) return 0;
        int left = postorderSum(root -> left, result);
        int right = postorderSum(root -> right, result);
        
        int tilt = abs(left - right);
        result += tilt;
        return left + right + root -> val;
    }
};