朴素想法
分开处理，回溯获取所有路径串，然后重建求和。
class Solution:def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:all_path=[]# 回溯获取所有路径def traceback(root,path):if not root:return path.append(str(root.val))if not root.right and not root.left:all_path.append("".join(path))traceback(root.left,path)traceback(root.right,path)path.pop()return path=[]traceback(root,path)# 组装获取结果ans= 0for path in all_path:num_string="".join(path)ans+=int(num_string,2)return ans
优化
可以在递归中直接处理。使用位运算方便快捷的将二进制转换为十进制。
class Solution:def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:def dfs(root,val):if not root:return 0# 当前路径对应的十进制值cur_val=(val<<1)|root.valif not root.left and not root.right:return cur_val# 对分支路径的结果求和，得到从根经过该节点到叶节点，所有路径的十进制和return dfs(root.left,cur_val)+dfs(root.right,cur_val)return dfs(root,0)
下面这个版本我觉得更好理解一点
class Solution:def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:ans=0def dfs(root,val=0):nonlocal ansif not root:return cur_val=(val<<1)|root.valif not root.left and not root.right:ans+=cur_valreturn cur_valdfs(root.left,cur_val)dfs(root.right,cur_val)dfs(root,0)