📘 題目敘述
給你一棵二元樹的根節點 root，其中每個節點的值都是 0 或 1。
每一條從根到葉節點的路徑，都可以視為一個二進位數字：路徑上節點的值依序組成二進位字串。
請回傳所有從根到葉節點的二進位數字轉成十進位後的總和。
條件限制
- 樹中節點的數量在範圍
[1, 1000] Node.val只會是0或1
🧠 解題思路
我用 DFS 走每一條從根到葉的路徑，並在走的過程中直接把「目前這條路徑代表的二進位數」算出來。
我用 now 表示走到目前節點時，路徑值對應的十進位數。
當我往下走一層時，相當於二進位左移一位再加上新節點的 bit：
now = now * 2 + child->val
這樣一路走到葉節點時，now 就是這條路徑的完整二進位值（轉成十進位後）。
當我走到葉節點（左右都沒有）時，我就把這條路徑的 now 加進總和 sum。
最後 DFS 跑完整棵樹後，sum 就是所有根到葉路徑的總和。
所有變數
sum：所有根到葉路徑的二進位值（十進位表示）總和now：目前 DFS 走到某個節點時，這條路徑累積出來的十進位值
🪜 主要流程步驟
1. 從根開始 DFS，now 初始就是 root->val
我在 sumRootToLeaf 裡直接呼叫：
count(root, root->val)
代表路徑一開始只有根節點，所以目前值就是根的 0/1。
2. 在 count(root, now) 中判斷是否到葉節點
如果 root 沒有左子樹也沒有右子樹，代表這個節點是葉節點。
這時 now 就是一條完整的根到葉二進位數，我直接：
sum += now
然後 return。
3. 否則往左右子樹遞迴，並更新 now
如果不是葉節點，我就看左右子樹是否存在：
- 如果有左子樹：
- 新的值是
now * 2 + root->left->val - 再遞迴
count(root->left, 新的值)
- 新的值是
- 如果有右子樹：
- 新的值是
now * 2 + root->right->val - 再遞迴
count(root->right, 新的值)
- 新的值是
這等價於二進位「左移一位」再接上下一個 bit。
4. DFS 結束後回傳 sum
所有路徑都被加進 sum 後，回傳 sum。
⏱️ 複雜度
- 時間複雜度：
O(n)
每個節點最多走訪一次。 - 空間複雜度：
O(h)
遞迴呼叫深度是樹高，最壞情況鏈狀樹是O(n)。
💻 程式碼實作
class Solution {
public:
int sum = 0;
void count(TreeNode* root, int now) {
if (!(root->left) && !(root->right)) {
sum += now;
return;
} else {
if (root->left) {
count(root->left, now * 2 + (root->left)->val);
}
if (root->right) {
count(root->right, now * 2 + (root->right)->val);
}
}
}
int sumRootToLeaf(TreeNode* root) {
count(root, root->val);
return sum;
}
};
🔗 題目連結
https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/