563. Binary Tree Tilt

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int result=0;
    
    public int findTilt(TreeNode root) {
        postOrder(root);
        return result;
    }
    
    private int postOrder(TreeNode root) {
        if(null==root) return 0;
        int left=postOrder(root.left);
        int right=postOrder(root.right);
        result+=Math.abs(left-right);
        return left+right+root.val;
    }
}

本题计算absolute difference. 简称ad

一个节点ad=左子树所有元素SUM 和  又子树所有元素SUM  差的绝对值.

一棵树ad=所有节点ad 求和.

所以很自然的就是考一个遍历而已.

唯一的难点是需要计算两个值,  例如节点A计算完自己的ad之后, A节点的父节点B如何计算?  所以还需要计算A的左右元素之和.