请写一个程序创建一棵二叉树,并按照一定规则,输出二叉树根节点到叶子节点的路径。
创新互联是一家专业提供上林企业网站建设,专注与成都网站设计、做网站、H5网站设计、小程序制作等业务。10年已为上林众多企业、政府机构等服务。创新互联专业网站建设公司优惠进行中。规则如下:
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))
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。