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

2022-01-11 94 words One minute

Contents

題目敘述

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 去尋訪，如果 !root->left && !root->right 就代表到達 leaf，直接回傳算出來的值。

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);
    }
};