563. Binary Tree Tilt

, 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int findTilt(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return tilt(root) + findTilt(root.left) + findTilt(root.right);
    }

    private int tilt(TreeNode node) {
        if (node == null) {
            return 0;
        }

        return Math.abs(nodeSum(node.left) - nodeSum(node.right));
    }

    private int nodeSum(TreeNode node) {
        if (node == null) {
            return 0;
        }

        return node.val + nodeSum(node.left) + nodeSum(node.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    private static class TiltHolder {
        private int tilt;
    }

    public int findTilt(TreeNode root) {
        TiltHolder tiltHolder = new TiltHolder();
        nodeSum(root, tiltHolder);
        return tiltHolder.tilt;
    }

    private int nodeSum(TreeNode node, TiltHolder tiltHolder) {
        if (node == null) {
            return 0;
        }

        int leftSum = nodeSum(node.left, tiltHolder);
        int rightSum = nodeSum(node.right, tiltHolder);

        tiltHolder.tilt += Math.abs(leftSum - rightSum);

        return node.val + leftSum + rightSum;
    }
}

References

563. Binary Tree Tilt