Binary Tree Tilt
Given the root of a binary tree, return the sum of every tree node's tilt.
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.
Input: root = [1,2,3]
Output: 1
Explanation:
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tile of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1This sounds like DFS. So let's start trying to recurse.
Our base case is that if the root is None, we return
And then we want to recurse both left and right trees.
While doing this, we want to sum each side. We can do that by storing them in these variables. And then we calculate the tilt:
Finally, when we have reached a leaf node we want it to return the sums of either side added to the current value.
Thus our solution is:
Last updated
Was this helpful?