The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if there the node does not have a right child.

Given a binary tree, return the sum of every tree node’s tilt.

Sample Input:

root = [5, 3, 7, 1, 4, None, 9 ]

Sample Output:

For the given tree:
Tilt of node 1 : 0
Tilt of node 4 : 0
Tilt of node 9 : 0
Tilt of node 3 : |1-4| = 3
Tilt of node 7 : |0-9| = 9
Tilt of node 5 : |(1+4+3)-(9+7)| = 8
Tilt of binary tree : 0 + 0 + 0 + 3 + 9 + 8 = 20

数据结构和算法：初级练习题 #42 – 二叉树倾斜度

给定一个二叉树，返回整棵树的倾斜度。

• 一个节点的倾斜度定义：左子树的所有节点和，与右子树所有节点和的绝对值差。空节点的倾斜度定义为0。
• 整棵树的倾斜度定义：所有节点的倾斜度之和。

输入样例：

root = [5, 3, 7, 1, 4, None, 9 ]

输出样例：

上面的二叉树中：
节点1的倾斜度 : 0
节点4的倾斜度 : 0
节点9的倾斜度 : 0
节点3的倾斜度 : |1-4| = 3
节点7的倾斜度 : |0-9| = 9
节点5的倾斜度 : |(1+4+3)-(9+7)| = 8
整颗树的倾斜度 : 0 + 0 + 0 + 3 + 9 + 8 = 20

Python Solution