概述
自己：https://sleepymonster.cn/
仓库：https://github.com/hengyi666
输入: [4,9,0,5,1]
4
/
9 0
/
5 1
数字总和 = 495 + 491 + 40 = 1026.
import collections
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.rigth = right
class SolutionDFS:
def sumNumbersA(self, root: TreeNode) -> int:
def DFS(root: TreeNode, prevTotal = 0) -> int:
if not root:
return 0
total = prevTotal * 10 + root.val
if not root.left and not root.rigth:
return total
else:
return DFS(root.left, total) + DFS(root.rigth, total)
return DFS(root)
class SolutionBFS:
def sumNumbersB(self,root:TreeNode) -> int:
if not root:
return 0
total =0
nodeQueue = collections.deque([root])
numQueue = collections.deque([root.val])
while nodeQueue:
node, num=nodeQueue.popleft(), numQueue.popleft()
left, right = node.left, node.rigth
if not node.left and not node.rigth:
total += num
else:
if node.left:
nodeQueue.append(node.left)
numQueue.append(num*10+left.val)
if node.rigth:
nodeQueue.append(node.rigth)
numQueue.append(num * 10 + right.val)
return total
root1 = TreeNode(1)
n2 = TreeNode(2)
n3 = TreeNode(3)
n4 = TreeNode(4)
n5 = TreeNode(5)
root1.left = n2
root1.rigth = n3
n2.left = n4
n2.rigth = n5
test1=SolutionDFS().sumNumbersA(root1)
print(test1)
test2=SolutionBFS().sumNumbersB(root1)
print(test2)
一起努力，可以的话点个赞吧QAQ
总结
以上是编程之家为你收集整理的【Python】求根到叶子节点数字之和(DFS&BFS)全部内容，希望文章能够帮你解决【Python】求根到叶子节点数字之和(DFS&BFS)所遇到的程序开发问题。
如果您也喜欢它,动动您的小指点个赞吧
602392714
清零编程群