leetcode 1022. Sum of Root To Leaf Binary Numbers [Easy]

題目敘述

Input: root = [1, 0, 1, 0, 1, 0, 1]

Output: 22

Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

給一棵節點值為 0 或 1 的 binary tree，回傳從 root 到各個 leaf 節點路徑所組成二進位數的總和。

解題紀錄

用 DFS 尋訪，每往下一層就把目前的值左移一位再加上當前節點值。到達 leaf（!root->left && !root->right）時直接回傳累積的結果。

class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        return solution(root, 0);
    }
    
    int solution(TreeNode *root, int bin) {
        if (!root) return 0;
        bin = (bin << 1) + root->val;
        if (!root->left && !root->right) return bin; 
        return solution(root->left, bin) + solution(root->right, bin);
    }
};