计算根节点到叶子节点的所组成的数字（1247， 125， 1367）以及叶子节点到根节点组成的数字（7421， 521， 8631），其二叉树树型结构如下
计算从根节点到叶子节点组成的数字，本质上来说就是二叉树的先序便利的变形，只在每次递归遍历过程中，将上一步计算的结果传到下一轮的递归预算中，其代码如下：
class Tree(object):
def __init__(self, val):
self.value = '%s' % str(val)
self.value = val
self.lchild = None
self.rchild = None
def __str__(self):
returnList = []
returnList.append(self)
for i in len(returnList):
node = returnList[i]
returnList.append(node.lchild)
returnList.append(node.rchild)
return str(returnList)
def _repr_(self):
return '<N:%s>' % self.value
def TreeSum(depth, value, tree):
if not tree.lchild and not tree.rchild:
print '%s value: %s' % (depth * '\t', value)
else:
#import pdb;pdb.set_trace()
if tree.lchild:
print '%sT%s->lchild --->>>' % (depth * '\t', tree.value)
TreeSum(depth+1, value * 10 + tree.lchild.value, tree.lchild)
if tree.rchild:
print '%sT%s->rchild %s' % (depth * '\t', tree.value, '--->>>'.decode().encode('GBK'))
TreeSum(depth+1, value * 10 + tree.rchild.value, tree.rchild)
def RTreeSum(depth, value, tree):
if tree.lchild or tree.rchild:
#import pdb;pdb.set_trace()
if tree.lchild:
print '%sT%s->lchild --->>>' % (depth * '\t', tree.lchild.value)
RTreeSum(depth+1, tree.lchild.value * pow(10, depth) + value, tree.lchild)
if tree.rchild:
print '%sT%s->rchild --->>>' % (depth * '\t', tree.rchild.value)
RTreeSum(depth+1, tree.rchild.value * pow(10, depth) + value, tree.rchild)
else:
print '%s value: %s' % (depth * '\t', value)
if __name__ == '__main__':
root = Tree(1)
t2 = Tree(2)
t3 = Tree(3)
t4 = Tree(4)
t5 = Tree(5)
t6 = Tree(6)
t7 = Tree(7)
t8 = Tree(8)
root.lchild = t2
root.rchild = t3
t2.lchild = t4
t2.rchild = t5
t3.lchild = None
t3.rchild = t6
t4.lchild = t7
t4.rchild = None
t6.rchild = t8
print 'Tree Sum:'
TreeSum(0, 1, root)
print 'Reverse Tree Sum:'
RTreeSum(1, 1, root)
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
其中TreeSum是计算跟节点到叶子节点的数字组合， RTreeSum 是计算叶子节点到根节点的组合
输出结果如下：
Tree Sum:
T1->lchild --->>>
T2->lchild --->>>
T4->lchild --->>>
value: 1247
T2->rchild --->>>
value: 125
T1->rchild --->>>
T3->rchild --->>>
T6->rchild --->>>
value: 1368
Reverse Tree Sum:
T2->lchild --->>>
T4->lchild --->>>
T7->lchild --->>>
value: 7421
T5->rchild --->>>
value: 521
T3->rchild --->>>
T6->rchild --->>>
T8->rchild --->>>
value: 8631