LeetCode1022-从根到叶的二进制数之和

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/

中文链接：https://leetcode-cn.com/problems/sum-of-root-to-leaf-binary-numbers/

题目详述

给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。

对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。

示例：

1
2
3
输入：[1,0,1,0,1,0,1]
输出：22
解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

提示：

  1. 树中的结点数介于 1 和 1000 之间。
  2. node.val 为 0 或 1 。
  3. 结果不会超过 2^31 - 1.

题目详解

运用 DFS 找到每条路径，并把路径上的数字转化为十进制数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_01022 {

    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int s) {
        if (root == null) {
            return 0;
        }
        s = s << 1 | root.val;
        if (root.left == null && root.right == null) {
            return s;
        }
        return dfs(root.left, s) + dfs(root.right, s);
    }
}