If we had each node's subtree sum, our answer would look like this psuedocode:
for each node: ans += abs(node.left.subtreesum - node.right.subtreesum). Let
_sum(node) be the node's subtree sum. We can find it by adding the subtree sum of the left child, plus the subtree sum of the right child, plus the node's value. While we are visiting the node (each node is visited exactly once), we might as well do the
ans += abs(left_sum - right_sum) part.
def findTilt(self, root): self.ans = 0 def _sum(node): if not node: return 0 left, right = _sum(node.left), _sum(node.right) self.ans += abs(left - right) return node.val + left + right _sum(root) return self.ans
@awice the 2nd to last statement, why using
search() here? Shouldn't it be
@ian34 correct, I fixed it
node.val along with the sum difference of left, right subtree values is brilliant, because the same value
node.val will be subtracted anyway. How to think of ideas like this?!?!
@ian34 node.val is not being subtracted. sum of all nodes left subtree and right subtree are being subtracted.
return node.val + left + right
is needed to simply calculate the left/right subtree's sum.
@sidharth you are right. The trick here is that the condition
null node has
0 tilt, which perfectly fits the statement where returning
0 as the value for a
null node. So the recursive function just simply return the sum of left, right subtree including itself, while recording the left, right difference.
@awice yes,you explanation is easy to understand,thx :)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.