563.md

Question:

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:

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.

Analysis

这道题是要求一棵树的坡度，而整颗树的坡度又是等于每个节点的坡度之和，单个节点的坡度呢，又是等于其左右子树的节点和之差的绝对值，那么问题有变成了如何求一棵树的节点和了，问题就简单了，直接写出来，就是解法一了。

解法二呢，算是一个小小的优化吧，这里利用了一个技巧，就是关于求节点累积结果时候，采用后序遍历会比较好，这样可以直接拿到左右的值，然后以此计算后，直接接续到结果就可以了。

Tips

求节点累积结果时候，采用后序遍历会比较好，这样可以直接拿到左右的值

Code

// 解法一

func absDiff(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

// 以t为根的树的所有的节点和
func sum(t *TreeNode) int {
	if t == nil {
		return 0
	}
	return t.Val + sum(t.Left) + sum(t.Right)
}

// t节点的坡度
func tilt(t *TreeNode) int {
	if t == nil {
		return 0
	}

	return absDiff(sum(t.Left), sum(t.Right))
}

func findTilt(root *TreeNode) int {
	if root == nil {
		return 0
	}

	return tilt(root) + findTilt(root.Left) + findTilt(root.Right)
}

// 解法二

func postOrder(root *TreeNode, res *int) int {
	if root == nil {
		return 0
	}

	leftSum := postOrder(root.Left, res)
	rightSum := postOrder(root.Right, res)

	*res += absDiff(leftSum, rightSum)
	return leftSum + rightSum + root.Val
}

func findTilt(root *TreeNode) int {
	var res int
	postOrder(root, &res)
	return res
}