Python实现最大子树问题

找出一个子树，使之结点的数值之和为最大！
View Code
 1 class tree_node(object):
 2     """docstring for TreeNode"""
 3     def __init__(self,val,left = None,right = None):
 4         self.val = val
 5         self.left = left
 6         self.right = right
 7 
 8 
 9 class attr_of_tree(object):
10     """docstring for list_node """
11     def __init__(self,is_positive,sum,root):
12         self.is_positive =  is_positive
13         self.sum = sum
14         self.root = root
15 
16 
17 
18 def get_max_sub_tree(root,flag = False):
19 
20     def f(root,l):
21         if root is None:
22             return attr_of_tree(True,0,root)
23         else:
24             left = f(root.left,l)
25             right = f(root.right,l)
26             attr = attr_of_tree(left.is_positive and right.is_positive and root.val > 0 , left.sum + right.sum + root.val , root)
27             l.append(attr)
28             return attr
29 
30     l = []
31     f(root,l)
32     if flag:
33         l = [i for i in l if i.is_positive]
34     return max(l,key = lambda x: x.sum).root
35 
36 
37 
38 def build_test_tree(l):
39     
40     def f(l,n):
41         if n > len(l)-1 or l[n] is None:
42             return None
43         else :
44             return tree_node(l[n],f(l,2*n+1),f(l,2*n+2))
45 
46     return f(l,0)
47 
48 
49 def print_tree(root):
50     if root is None:
51         return
52     else:
53         print root.val
54         print_tree(root.left)
55         print_tree(root.right)
56 
57 
58 
59 def main():
60     root = build_test_tree( [0,-7,2,3,4,-4,3,4] )
61     print "=========================="
62     ret = get_max_sub_tree(root)
63     print_tree(ret)
64 
65     root = build_test_tree( [0,-10,2,3,4,1,3,4,-1] )
66     print "=========================="
67     ret = get_max_sub_tree(root)
68     print_tree(ret)
69 
70     root = build_test_tree( [0,-10,2,3,4,1,3,4,-1] )
71     print "=========================="
72     ret = get_max_sub_tree(root,True)
73     print_tree(ret)
74 
75 
76 
77 
78 
79 
80 if __name__ == '__main__':
81     main()