Minimum Subtree

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