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

The tilt of the whole tree

Example:

Input:

1

/ \

2 3

Output: 1

Explanation:

Note:

1. The sum of node values in any subtree won’t exceed the range of 32-bit integer.
2. All the tilt values won’t exceed the range of 32-bit integer.

方法1：递归的方式，一边累加tilt的值，一边求左、右子树的和。代码如下。一个很明显的问题是，在求左右子树和时，树被遍历了多次。比如，求1的左右子树和时，需要遍历2、4、5、3；在求2的左右子树和时需要遍历4、5，可见4、5被遍历了两遍。

public static int findTilt(TreeNode root) {
     if(root == null) {
         return 0;
     }
     return findTilt(root.left) + findTilt(root.right) + 
            Math.abs(sum(root.left) - sum(root.right));
}

public static int sum(TreeNode root) {
     if(root == null) {
         return 0;
     }
     return root.val + sum(root.left) + sum(root.right); 
}      

int tilt = 0;

    public int findTilt(TreeNode root) {
        sum(root);
        return tilt;
    }

    public int sum(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int l = sum(root.left);
        int r = sum(root.right);
        tilt += Math.abs(l - r);
        return