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