# 1022. 從根到葉的二進制數之和 [DFS] [EASY]
給出一棵二叉樹，其上每個結點的值都是 0 或 1 。每一條從根到葉的路徑都代表一個從最高有效位開始的二進制數。

例如，如果路徑為 0 -> 1 -> 1 -> 0 -> 1，那麽它表示二進制數 01101，也就是 13 。
對樹上的每一片葉子，我們都要找出從根到該葉子的路徑所表示的數字。

返回這些數字之和。題目數據保證答案是一個 32 位 整數。


示例 1：

輸入：root = [1,0,1,0,1,0,1]
輸出：22
解釋：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

示例 2：

輸入：root = [0]
輸出：0

**題解思路**

1. 確定輸入參數及回傳值
2. 使用dfs走訪每個節點，並把值傳給孩子節點
3. 終止條件：當前節點如果為空回傳0
4. 當前節點如果有子數，走訪到父節點的路徑加上計算用到上個節點的計算結果。
5. 如果當前節點是葉節點，回傳計算從2進轉換十進結果。
6. 如果當前節點不是葉節點，回傳左子數加右子數對應結果的和。

程式碼：

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

    private int dfs(TreeNode node, int cur) {
        if(node == null) return 0;
        cur = cur *2 + node.val;
        return node.right == node.left ? cur : dfs(node.left, cur) + dfs(node.right, cur);
    }
}