[LeetCode] 1022. Sum of Root To Leaf Binary Numbers

[grandyang]

You are given the root of a binary tree where each node has a value 0 or 1.  Each root-to-leaf path represents a binary number starting with the most significant bit.  For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf.

Return  the sum of these numbers. The answer is guaranteed to fit in a 32-bits integer.

Example 1:

Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Example 2:

Input: root = [0]
Output: 0

Example 3:

Input: root = [1]
Output: 1

Example 4:

Input: root = [1,1]
Output: 3

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• Node.val is 0 or 1.

这道题给了一个结点值为0或1的二叉树，让返回所有从根结点到叶结点的路径组成的二进制数字的和。实际上就是一道变形的路径之和的题目，关于路径之和，LeetCode 有很多道题目，比如 Path Sum IV，Path Sum III，Binary Tree Maximum Path Sum，Path Sum II，Path Sum，和 Minimum Path Sum 等等。还是要用递归来做，就使用先序遍历就可以了，使用一个变量 cur 记录从根结点到当前结点的路径的二进制数对应的十进制的值，每当新加一个结点时，当前的数字要左移一位，也就是乘以2，再加上当前的结点值。若当前结点是个叶结点，则说明一条完整的路径已经找到了，将数字加入结果 res，然后对左右子结点分别调用递归函数即可，参见代码如下：

解法一：

class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        int res = 0;
        helper(root, 0, res);
        return res;
    }
    void helper(TreeNode* node, int cur, int& res) {
        if (!node) return;
        cur = cur * 2 + node->val;
        if (!node->left && !node->right) {
            res += cur;
        }
        helper(node->left, cur, res);
        helper(node->right, cur, res);
    }
};

我们也可以写的更简洁一些，让 helper 函数返回路径之和的值，这样在更新完 cur 之和，只要判断是否是叶结点，是的话直接返回 cur，否则返回对左右子结点调用递归函数的返回值之和即可，参见代码如下：

解法二：

class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        return helper(root, 0);
    }
    int helper(TreeNode* node, int cur) {
        if (!node) return 0;
        cur = cur * 2 + node->val;
        return node->left == node->right ? cur : helper(node->left, cur) + helper(node->right, cur);
    }
};

Github 同步地址:

#1022

类似题目：

Path Sum IV

Path Sum III

Binary Tree Maximum Path Sum

Path Sum II

Path Sum

Minimum Path Sum

参考资料：

https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/

https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/discuss/270600/Java-Simple-DFS

https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/discuss/270025/JavaC%2B%2BPython-Recursive-Solution

LeetCode All in One 题目讲解汇总(持续更新中...)