Given a binary tree, find the subtree with minimum sum. Return the root of the subtree.
Notice
LintCode will print the subtree which root is your return node.
It's guaranteed that there is only one subtree with minimum sum and the given binary tree is not an empty tree.
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""
class Solution:
# @param {TreeNode} root the root of binary tree
# @return {TreeNode} the root of the minimum subtree
import sys
min_weight = sys.maxint
result = None
def findSubtree(self, root):
# Write your code here
self.mintree(root)
return self.result
def mintree(self, root):
if not root:
return 0
left = self.mintree(root.left)
right = self.mintree(root.right)
if left+right+root.val<=self.min_weight:
self.min_weight = left+right+root.val
self.result = root
return left+right+root.val