力扣每日一题 20260224

281 words

1 minute

力扣每日一题 20260224

2026-02-24

leetcode

1022. 从根到叶的二进制数之和#

考虑已有二进制数 $x$ 在低位新增一位可以写成 x << 1 + 新增位 ，我们可以在二叉树上 dfs 去完成这个过程，从而解决这道题。

许多初学者觉得理解递归或者 dfs 很难，主播个人认为可以跳过理解 dfs 工作的过程，直接去考虑当前这道题所需要的 dfs 的作用，比如：传入的参数是什么，返回值返回的是什么。然后直接拿 dfs 当作一个黑盒去用。

例如本题我们可以这样设计 dfs：他传入的参数是当前的节点和自顶向下递归的过程中当前的数字。而返回值是已当前节点为根的子树的累加和。

这是时候我们就可以发现：

dfs(root,\ x)=dfs(root→left,\ 2x+当前位)+dfs(root→right,\ 2x+当前位)

代码：

1
class Solution {
2
public:
3
    int dfs(TreeNode* root, int x) {
4
        if (root == nullptr) return 0;
5
        x = (x << 1) + root->val;
6
        if (root->left == nullptr && root->right == nullptr) return x;
7
        return dfs(root->left, x) + dfs(root->right, x);
8
    }
9

10
    int sumRootToLeaf(TreeNode* root) {
11
        return dfs(root, 0);
12
    }
13
};