LeetCode 1022. 从根到叶的二进制之和 超详细技术解析Python前言本题是 LeetCode 第 1022 号问题属于二叉树遍历与二进制转换的结合题难度简单但高频。核心考察二叉树的深度优先遍历DFS、广度优先遍历BFS思路以及二进制数到十进制数的实时转换技巧是面试中基础且典型的二叉树应用题。本文将从题目描述入手拆解核心考点提供两种主流解题方案DFS递归、BFS迭代严格遵循题目要求的代码格式逐行解析代码逻辑结合示例验证正确性补充复杂度分析和易错点提示适合Python初学者、算法入门者以及二叉树遍历基础薄弱的同学参考。题目描述给出一棵二叉树其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如如果路径为 0 - 1 - 1 - 0 - 1那么它表示二进制数 01101也就是 13 。对树上的每一片叶子我们都要找出从根到该叶子的路径所表示的数字。返回这些数字之和。题目数据保证答案是一个 32 位 整数。示例示例 1输入root[1,0,1,0,1,0,1]输出22解释(100)(101)(110)(111)456722补充说明二叉树结构为根节点1左子节点0左子树0、右子树1右子节点1左子树0、右子树1四条根到叶路径分别对应二进制100、101、110、111转换为十进制求和得22。示例 2输入root[0]输出0解释仅一条根到叶路径二进制为0十进制为0和为0。提示树中的节点数在 [1, 1000] 范围内Node.val 仅为 0 或 1解题思路分析核心问题拆解本题的核心是两个关键步骤二者需结合进行遍历二叉树找到所有「根到叶」的路径叶节点左右子节点均为None的节点将每条路径上的节点值0/1组成二进制数转换为十进制数最终求和。关键技巧二进制数实时转换无需存储完整路径。对于任意一条路径从根到当前节点的二进制数可通过「当前值 × 2 节点值」的方式实时计算避免存储路径后再转换节省空间且提高效率。示例路径 1-0-1实时计算过程为1 → 1×202 → 2×215对应二进制101十进制5与直接转换结果一致。两种主流解题方案二叉树遍历的核心思路有两种对应本题的两种解题方案各有优势可根据自身掌握程度选择方案1深度优先遍历DFS- 递归实现思路从根节点出发递归遍历左、右子树实时计算当前路径的十进制值。当遍历到叶节点时将当前路径的十进制值加入总和。优势代码简洁、逻辑直观无需额外维护栈结构适合快速编写符合递归思维习惯。方案2广度优先遍历BFS- 迭代实现思路使用队列存储「当前节点」和「当前路径的十进制值」依次出队每个节点更新其左右子节点的路径值若为叶节点则累加求和直至队列为空。优势避免递归栈溢出风险虽然本题节点数最多1000递归无压力但迭代思路更通用逻辑清晰适合理解二叉树的层次遍历思想。核心注意点叶节点判断必须是「左右子节点均为None」仅一个子节点为空不算叶节点路径计算严格遵循「最高有效位在前」即根节点是二进制数的最高位后续节点依次为低位实时计算公式「current_sum current_sum × 2 node.val」不可颠倒边界处理当树只有一个节点根节点即为叶节点时直接返回该节点的值0或1。完整代码实现两种方案本文提供两种实现方案均严格遵循题目要求的代码格式包含TreeNode类注释、Solution类及指定方法可直接复制提交到LeetCode适配Python3环境。方案1DFS递归实现简洁直观推荐日常使用# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defsumRootToLeaf(self,root:Optional[TreeNode])-int:# 递归辅助函数参数为当前节点、当前路径的十进制和defdfs(node,current_sum):# 终止条件节点为空返回0无有效路径ifnotnode:return0# 实时更新当前路径的十进制和current_sumcurrent_sum*2node.val# 终止条件当前节点是叶节点返回当前路径和ifnotnode.leftandnotnode.right:returncurrent_sum# 递归遍历左子树和右子树求和返回returndfs(node.left,current_sum)dfs(node.right,current_sum)# 从根节点开始初始路径和为0returndfs(root,0)方案2BFS迭代实现通用稳定避免递归溢出# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightfromcollectionsimportdequeclassSolution:defsumRootToLeaf(self,root:Optional[TreeNode])-int:# 边界处理树为空题目提示节点数≥1可省略但增加鲁棒性ifnotroot:return0# 队列存储 (当前节点, 当前路径十进制和)初始入队根节点路径和为0queuedeque([(root,0)])total_sum0whilequeue:# 出队当前节点和对应路径和node,current_sumqueue.popleft()# 实时更新路径和current_sumcurrent_sum*2node.val# 判断是否为叶节点若是则加入总和ifnotnode.leftandnotnode.right:total_sumcurrent_sumcontinue# 左子节点不为空入队ifnode.left:queue.append((node.left,current_sum))# 右子节点不为空入队ifnode.right:queue.append((node.right,current_sum))returntotal_sum代码逐行解析通用部分解析两种方案均适用# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right right说明LeetCode官方给定的二叉树节点类无需修改直接沿用即可。其中val为节点值0或1left和right分别为左、右子节点。classSolution:defsumRootToLeaf(self,root:Optional[TreeNode])-int:说明严格遵循题目要求的类名Solution、方法名sumRootToLeaf、参数root: Optional[TreeNode]和返回值类型int可直接提交无需调整。方案1DFS递归逐行解析defdfs(node,current_sum):# 终止条件节点为空返回0无有效路径ifnotnode:return0# 实时更新当前路径的十进制和current_sumcurrent_sum*2node.val# 终止条件当前节点是叶节点返回当前路径和ifnotnode.leftandnotnode.right:returncurrent_sum# 递归遍历左子树和右子树求和返回returndfs(node.left,current_sum)dfs(node.right,current_sum)递归函数定义dfs(node, current_sum)node为当前遍历的节点current_sum为从根节点到当前节点的路径对应的十进制和终止条件1if not node: return 0当节点为空时说明该路径无效如叶节点的空左/右子节点返回0不影响总和核心计算current_sum current_sum * 2 node.val将当前节点值加入路径二进制转十进制的核心逻辑左移1位等价于×2加上当前节点值即为新的十进制和终止条件2if not node.left and not node.right: return current_sum当前节点为叶节点时返回该路径的十进制和供上层递归累加递归逻辑return dfs(node.left, current_sum) dfs(node.right, current_sum)递归遍历左、右子树将两条子树的路径和相加得到当前节点的总路径和。returndfs(root,0)说明从根节点开始递归初始路径和为0根节点之前无节点路径为空十进制和为0。方案2BFS迭代逐行解析fromcollectionsimportdeque# 导入队列用于BFS遍历说明Python的collections.deque是双端队列popleft()操作时间复杂度为O(1)比列表的pop(0)更高效适合BFS遍历。ifnotroot:return0说明边界处理虽然题目提示树中节点数≥1但增加该判断可提升代码鲁棒性避免异常。queuedeque([(root,0)])total_sum0说明队列初始化存储元组(当前节点, 当前路径十进制和)初始入队根节点路径和为0total_sum用于累加所有根到叶路径的十进制和。whilequeue:# 出队当前节点和对应路径和node,current_sumqueue.popleft()# 实时更新路径和current_sumcurrent_sum*2node.val# 判断是否为叶节点若是则加入总和ifnotnode.leftandnotnode.right:total_sumcurrent_sumcontinue# 左子节点不为空入队ifnode.left:queue.append((node.left,current_sum))# 右子节点不为空入队ifnode.right:queue.append((node.right,current_sum))循环条件while queue队列不为空时持续遍历出队操作node, current_sum queue.popleft()取出队首节点和对应的路径和路径更新与递归方案一致current_sum current_sum * 2 node.val实时计算当前路径和叶节点判断若当前节点为叶节点将路径和加入total_sum跳过后续子节点入队操作子节点入队左、右子节点不为空时分别入队携带当前更新后的路径和供后续遍历。returntotal_sum说明遍历结束后total_sum即为所有根到叶路径的二进制数对应的十进制和返回即可。示例验证确保结果正确验证示例1输入root [1,0,1,0,1,0,1]二叉树结构1为根左子树0右子树10的左子树0、右子树11的左子树0、右子树1DFS递归验证过程初始调用dfs(1, 0) → current_sum 0×211非叶节点递归左子树0和右子树1左子树0dfs(0, 1) → current_sum1×202非叶节点递归左子树0和右子树1左子树0的总和459左子树0dfs(0, 2) → current_sum2×204叶节点返回4右子树1dfs(1, 2) → current_sum2×215叶节点返回5右子树1dfs(1, 1) → current_sum1×213非叶节点递归左子树0和右子树1右子树1的总和6713左子树0dfs(0, 3) → current_sum3×206叶节点返回6右子树1dfs(1, 3) → current_sum3×217叶节点返回7总总和91322与示例输出一致 ✔️。验证示例2输入root [0]根节点即为叶节点DFS递归调用dfs(0, 0) → current_sum0×200叶节点返回0BFS迭代队列初始入队(0, 0)出队后current_sum0叶节点total_sum0输出0与示例一致 ✔️。复杂度分析时间复杂度两种方案的时间复杂度一致O(n)O(n)O(n)其中n为二叉树的节点数。DFS递归每个节点被访问一次递归调用次数等于节点数每次递归操作的时间复杂度为O(1)BFS迭代每个节点入队、出队各一次每次操作的时间复杂度为O(1)总操作次数为O(n)。注题目中节点数最多1000两种方案均能高效运行无超时风险。空间复杂度DFS递归O(h)O(h)O(h)h为二叉树的高度。递归栈的深度等于树的高度最坏情况下二叉树为单链h n空间复杂度为O(n)最好情况下二叉树为完全二叉树h log n空间复杂度为O(log n)。BFS迭代O(n)O(n)O(n)队列存储的节点数最多为二叉树的最大层节点数最坏情况下完全二叉树的最后一层节点数为n/2空间复杂度为O(n)。易错点与注意事项叶节点判断错误误将「只有一个子节点为空」的节点当作叶节点如节点有左子树、无右子树不算叶节点会导致路径计算错误正确判断应为「left和right均为None」。路径计算顺序颠倒误写为current_sum current_sum node.val × 2导致二进制位顺序错误低位在前、高位在后最终结果完全错误。递归终止条件遗漏忘记判断「node为空」的情况会导致递归报错AttributeError: ‘NoneType’ object has no attribute ‘val’。BFS队列初始化错误初始路径和设为root.val而非0会导致根节点值被重复计算如示例2中初始sum设为0计算后为0若初始设为0.val0结果正确但逻辑不严谨复杂树会出错。类型注解遗漏忘记给root参数添加Optional[TreeNode]注解LeetCode提交虽不报错但不符合Python规范也不符合题目要求的代码格式。总结本题的核心是「二叉树遍历」与「二进制转十进制」的结合关键在于「实时计算路径的十进制和」避免存储完整路径提升效率和节省空间。两种解题方案对比DFS递归代码简洁、逻辑直观适合快速编写适合面试时快速答题BFS迭代避免递归栈溢出逻辑更通用适合理解二叉树的层次遍历适合处理节点数极多的二叉树。本题适合作为二叉树遍历的入门练习既考察了DFS/BFS的核心思路又结合了二进制转换的基础知识点覆盖了面试中常见的基础考点。建议两种方案都掌握灵活应对不同的答题场景。此外本题可延伸练习若节点值为0-9求根到叶的十进制数之和解题思路完全一致仅需将「×2」改为「×10」即可可自行拓展练习。如有疑问欢迎在评论区留言交流一起探讨更优解法