document.write('
可以通过对二叉树的遍历找出所有的路径,然后判断各条路径上所有结点的值的和是否与给定的整数相
等,如果相等,则打印出这条路径。具体实现方法可以通过对二叉树进行先序遍历来实现,实现思路
为:对二叉树进行先序遍历,把遍历的路径记录下来,当遍历到叶子结点时,判断当前的路径上所有结
点数据的和是否等于给定的整数,如果相等则输出路径信息,示例代码如下:
class BiTNode:
def __init__(self):
self.data=None
self.lchild=None
self.rchild=None
"""
方法功能: 打印出满足所有结点数据的和等于num的所有路径
参数: root:二叉树根结点; num:给定的整数; sum:当前路径上所有结点的和
用来存储从根结点到当前遍历到结点的路径
"""
def FindRoad(root,num,sums,v):
#记录当前遍历的root结点
sums+=root.data
v.append(root.data)
#当前结点是叶子结点且遍历的路径上所有结点的和等于num
if root.lchild==None and root.rchild==None and sums==num:
i=0
while i<len(v):
print v[i],
i+=1
print \'\\n\'
#遍历root的左子树
if root.lchild!=None:
FindRoad(root.lchild,num,sums,v)
#遍历root的右予树
if root.rchild!=None:
FindRoad(root.rchild,num,sums,v)
#清除遍历的路径
sums-=v[-1]
v.remove(v[-1])
def constructTree():
root=BiTNode()
node1=BiTNode()
node2=BiTNode()
node3=BiTNode()
node4=BiTNode()
root.data=6
node1.data=3
node2.data=-7
node3.data=-1
node4.data=9
root.lchild=node1
root.rchild=node2
nodel.lchild=node3
nodel.rchild=node4
node2.lchild=node2.rchild=node3.lchild=node3.rchild=node4.lchild=node4.rchild=None
return root
if __name__=="__main__":
root=constructTree()
s=[]
print "满足路径结点和等于8的路径为:",
FindRoad (root,8,0,s)
程序的运行结果为:
满足路径结点和等于8的路径为:6 3 -1
算法性能分析:
这种方法与二叉树的先序遍历有着相同的时间复杂度O(N),此外,这种方法用一个数组存放遍历路
径上结点的值,在最坏的情况下时间复杂度为O(N)(所有结点只有左子树,或所有结点只有右子树),因
此,空间复杂度为O(N)。
');