BinaryTreeTilt [source code]

public class BinaryTreeTilt {
    private int res = 0; 

    public int findTilt(TreeNode root) {
        go(root);
        return res;
    }

    private int go(TreeNode root) {
        if (root == null) return 0;
        int leftSum = go(root.left);
        int rightSum = go(root.right);
        res += Math.abs(rightSum - leftSum);
        return root.val + leftSum + rightSum;
    }
}

总体就是一个传统的recursive tree问题. 这种问题的思路已经很清晰了, 就是要注意一下几个地方:

1. base case. 所谓 recursion, 一定不能忘记处理 base;
2. recursive return value. 没一层return 的到底是什么东西; 这一题就是一个例子, 这里 recurse 返回的东西并不是最后直接需要的结果. 另外, 因为JAVA 不支持multiple return values, 所以这里最后 res 用一个类似 global var 的做法来实现;
3. recursion 的顺序是 DFS, 这个不能忘记, 记住这个才能知道每一个 iteration 里面不同 line 之间的顺序关系怎么决定;

另外这里这个abs刚开始我没有加, 认为 BST 反正 sorted, 所以没有必要. 这个是没有考虑到假如 left 有 value, 但是 right 是 null 的情况;

速度是8ms, 73%, 差强人意;
submission 最优解是7ms, 其实代码跟我的是完全一样的, 一个post order traversal就结束了; 不知道为什么比我的快1ms;
discussion 好像也没有什么更好的解法;

Problem Description

Given a binary tree, return the tilt of the whole tree.

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.

The tilt of the whole tree is defined as the sum of all nodes' tilt.

Example:
Input:
1
/ \
2 3
Output: 1
Explanation:
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1
Note:

The sum of node values in any subtree won't exceed the range of 32-bit integer.
All the tilt values won't exceed the range of 32-bit integer.
Difficulty:Easy
Category:Algorithms
Acceptance:46.92%
Contributor: fallcreek
Companines
Indeed
Related Topics
tree