# 563 Binary Tree Tilt

Given a binary tree, return the tilt of thewhole tree.
The tilt of atree nodeis defined as theabsolute differencebetween 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 thewhole treeis 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. 1.
The sum of node values in any subtree won't exceed the range of 32-bit integer.
2. 2.
All the tilt values won't exceed the range of 32-bit integer.
Performance: O(N) time and space
The Idea: Because summations are have the property to be associative, we can use dynamic programming to first build a accumulation tree. With accumulation trees, every node is the summation of itself and its left and right subtrees. Using post order traversal, we can achieve this is O(N) time. Next, iterating through this accumation tree, we do another post order traversal that accumulations the absolute difference between the left and right subtrees. This also runs in O(N) time because the accumulation tree provides the summation of the left and right subtrees.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def build_cum_tree(self, node):
"""
:type node: TreeNode
:rtype: void
"""
# perform a postorder traversal through
# the tree and accumulate nodes
if (node != None):
self.build_cum_tree(node.left)
self.build_cum_tree(node.right)
if (node.left != None):
node.val += node.left.val
if (node.right != None):
node.val += node.right.val
def _findTilt(self, node, accumulator):
"""
:type root: TreeNode
:rtype: void
"""
if (node != None):
self._findTilt(node.left, accumulator)
self._findTilt(node.right, accumulator)
temp_sum = 0
if(node.left != None):
temp_sum += node.left.val
if(node.right != None):
temp_sum -= node.right.val
accumulator[0] += abs(temp_sum)
def findTilt(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# modify tree into dp accumulated tree
self.build_cum_tree(root)
# now traverse through tree again and
# to find |left_sub - right_sub|
#pre_order(root)
#print()
accumulator = [0]
self._findTilt(root, accumulator)
return accumulator[0]
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class BTree:
def __init__(self):
self.root = None
def getRoot(self):
return self.root
if(self.root == None):
self.root = TreeNode(val)
else:
if(val < node.val):
if(node.left != None):
else:
node.left = TreeNode(val)
else:
if(node.right != None):
else:
node.right = TreeNode(val)
def find(self, val):
if(self.root != None):
return self._find(val, self.root)
else:
return None
def _find(self, val, node):
if(val == node.val):
return node
elif(val < node.val and node.left != None):
self._find(val, node.l)
elif(val > node.val and node.right != None):
self._find(val, node.right)
def deleteTree(self):
# garbage collector will do this for us.
self.root = None
def printTree(self):
if(self.root != None):
self._printTree(self.root)
def _printTree(self, node):
if(node != None):
self._printTree(node.left)
print(str(node.val) + ' ')
self._printTree(node.right)
def pre_order(root):
"""
:type root: TreeNode
:rtype: void
"""
if (root != None):
pre_order(root.left)
print(str(root.val) + ' ', end='', flush=True )
pre_order(root.right)
if __name__ == '__main__':
# 3
# 0 4
# 2 8
tree = BTree()