python3实现在二叉树中找出和为某一值的所有路径(推荐)
时间：2021-04-18 09:50:08|栏目：Python代码|点击： 次
请写一个程序创建一棵二叉树，并按照一定规则，输出二叉树根节点到叶子节点的路径。
规则如下：
1、从最顶端的根结点，到最下面的叶子节点，计算路径通过的所有节点的和，如果与设置的某一值的相同，那么输出这条路径上的所有节点。
2、从根节点遍历树时，请请按照左到右遍历，即优先访问左子树的节点。
二叉树创建规则：从上到下一层一层的，按照从左到右的顺序进行构造
输入"10,5,12,4,7"值，构造的树如下：
1） 10
2） 10
/
5
3） 10
/\
5 12
4） 10
/\
5 12
/
4
5） 10
/\
5 12
/\
4 7
针对上面的二叉树，如果当前我们设置的“路径和”为19，那么输出结果为:
10,5,4
如果有多个路径，按到左到右的顺序遍历生成的结果每行显示一个显示。例如如果当前我们设置的“路径和”为22，那么
输出结果为:
10,5,7
10,12
如果没有找到路径和为设置的值的路径，输出error。
三、输入:
输入整数N---路径和
一行字符串，多个正整数，之间用","隔开
四、输出: 满足条件的二叉树路径
五、样例输入:
22
10,5,12,4,7
六、样例输出:
10,5,7
10,12
demo：
class Node(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Tree(object):
lt = [] # 依次存放左右孩子未满的节点
def __init__(self):
self.root = None
def add(self, number):
node = Node(number) # 将输入的数字节点化，使其具有左右孩子的属性
if self.root == None:
self.root = node
Tree.lt.append(self.root)
else:
while True:
point = Tree.lt[0] # 依次对左右孩子未满的节点分配孩子
if point.left ==None:
point.left = node
Tree.lt.append(point.left) # 该节点后面作为父节点也是未满的，也要加入到列表中。
return
elif point.right ==None:
point.right = node
Tree.lt.append(point.right) # 与左孩子同理
Tree.lt.pop(0) # 表示该节点已拥有左右孩子，从未满列表中去除
return
class Solution:
def __init__(self):
self.results = []
def RecursionFindPath(self, root, expectNumber, result):
result.append(root.val)
if root.left == None and root.right == None and sum(result) == expectNumber:
self.results.append(result)
temp = result[:]
if root.left:
self.RecursionFindPath(root.left, expectNumber, result)
result = temp[:]
if root.right:
self.RecursionFindPath(root.right, expectNumber, result)
def FindPath(self, root, expectNumber):
if root == None:
return []
self.RecursionFindPath(root, expectNumber, [])
self.results = sorted(self.results, key=len, reverse=True)
return self.results
if __name__ =='__main__':
t = Tree() # 二叉树类的实例化
L = [10, 5, 12, 4, 7]
for i in L:
t.add(i)
expectNum = 22
print(Solution().FindPath(t.root, expectNum))
输出样例：
总结
