LeetCode 题解工作台
从根到叶的二进制数之和
给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。 例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1 ，那么它表示二进制数 01101 ，也就是 13 。 对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。 返回这…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 二分·树·traversal
答案摘要
我们设计一个递归函数 $\text{dfs}(root, t)$，它接收两个参数：当前节点 和当前节点的父节点对应的二进制数 。函数的返回值是从当前节点到叶子节点的路径所表示的二进制数之和。答案即为 $\textrm{dfs}(root, 0)$。 递归函数的逻辑如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
- 例如，如果路径为
0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数01101，也就是13。
对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
返回这些数字之和。题目数据保证答案是一个 32 位 整数。
示例 1：
输入：root = [1,0,1,0,1,0,1] 输出：22 解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
示例 2：
输入：root = [0] 输出：0
提示：
- 树中的节点数在
[1, 1000]范围内 Node.val仅为0或1
解题思路
方法一：递归
我们设计一个递归函数 ，它接收两个参数：当前节点 和当前节点的父节点对应的二进制数 。函数的返回值是从当前节点到叶子节点的路径所表示的二进制数之和。答案即为 。
递归函数的逻辑如下：
- 如果当前节点 为空，则返回 ，否则计算当前节点对应的二进制数 ，即 。
- 如果当前节点是叶子节点，则返回 ，否则返回 和 的和。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点数。对每个节点访问一次；递归栈需要 的空间。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
def dfs(root: Optional[TreeNode], x: int) -> int:
if root is None:
return 0
x = x << 1 | root.val
if root.left == root.right:
return x
return dfs(root.left, x) + dfs(root.right, x)
return dfs(root, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tests depth-first traversal understanding and binary tree manipulation.
- question_mark
Evaluates candidate's ability to manage recursive state and path tracking.
- question_mark
Requires proficiency in converting binary representations to decimal.
常见陷阱
外企场景- error
Failing to handle tree nodes correctly, especially when transitioning from one binary number to another.
- error
Not correctly converting the binary number to decimal or mishandling the sum.
- error
Incorrectly managing recursion depth or state during backtracking, leading to incorrect results.
进阶变体
外企场景- arrow_right_alt
Use a breadth-first search (BFS) instead of DFS for tree traversal.
- arrow_right_alt
Consider a solution where you track the path using a list and convert at the end of the traversal.
- arrow_right_alt
Implement an iterative DFS using an explicit stack to avoid recursion.