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:
這道題給了一個結點值為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 同步地址:
https://github.com/grandyang/leetcode/issues/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 題目講解匯總(持續更新中...)