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 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

[暴力解法]：

时间分析：

空间分析：

［奇葩输出条件］：

理解DFS的返回值适用于所有点，ans[0]的返回值只适用于root一个点

［奇葩corner case］：

［思维问题］：

以为要用hashmap把每个点的距离差都存起来，但其实用traverse的参数就能实现自动记录

［一句话思路］：

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

DFS 的第一步别忘了写退出条件，树中是root == null

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

traverse(节点，ans[0])，可以自动记录每个附带的值

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［关键模板化代码］：

DFS先退出：

public int dfs(TreeNode root, int[] ans) {
        //exit
        if (root == null) {
            return 0;
        }
        //expand
        int left = dfs(root.left, ans);
        int right = dfs(root.right, ans);
        
        ans[0] += Math.abs(left - right);
        //return
        return left + right + root.val;
    }

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findTilt(TreeNode root) {
        //corner case
        if (root == null) {
            return 0;
        }
        int[] ans = new int[1];
        dfs(root, ans);
        //return
        return ans[0];
    }
    
    public int dfs(TreeNode root, int[] ans) {
        //exit
        if (root == null) {
            return 0;
        }
        //expand
        int left = dfs(root.left, ans);
        int right = dfs(root.right, ans);
        
        ans[0] += Math.abs(left - right);
        //return
        return left + right + root.val;
    }
}

View Code

563. Binary Tree Tilt 子节点差的绝对值之和

推荐阅读