563. Binary Tree Tilt #

Problem #

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.

Problem Summary #

Given a binary tree, calculate the tilt of the whole tree. The tilt of a tree node is defined as the absolute difference between the sum of the nodes in the left subtree and the sum of the nodes in the right subtree. The tilt of an empty node is 0. The tilt of the whole tree is the sum of the tilts of all its nodes.

Note:

1. The sum of the nodes in any subtree will not exceed the range of a 32-bit integer.
2. The tilt values will not exceed the range of a 32-bit integer.

Solution Ideas #

• Given a tree, calculate the accumulated sum of each node’s “tilt”. The definition of “tilt” is: the absolute value of the difference between the node value sums of the left subtree and the right subtree.
• Although this is an easy problem, if you misunderstand the “tilt” in the problem, you will get it wrong. The “tilt” is calculated as the difference between the sum of the values of all nodes in the left subtree and the sum of the values of all nodes in the right subtree. It is not simply the difference between the value of a node’s left child and the value of its right child. Once this point is clear, this problem becomes easy.

Code #

package leetcode

import "math"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findTilt(root *TreeNode) int {
	if root == nil {
		return 0
	}
	sum := 0
	findTiltDFS(root, &sum)
	return sum
}

func findTiltDFS(root *TreeNode, sum *int) int {
	if root == nil {
		return 0
	}
	left := findTiltDFS(root.Left, sum)
	right := findTiltDFS(root.Right, sum)
	*sum += int(math.Abs(float64(left) - float64(right)))
	return root.Val + left + right
}