LeetCode挑戦日記：Day36

はじめに

最近、業務で実装する時間よりも資料作成やレビューをする時間が多くなってきました。
このままでは自身のコーディング能力が落ちそうで怖いので、LeetCodeを始めてみました。

自身の学習の記録 & LeetCodeに興味のある人が挑戦しやすいように、記事に残していきます。
このような競技プログラミングをした経験がないので、ひよってEasyからやっていきます...

[Medium] 437. Path Sum III

二分木の根と整数targetSumが与えられたとき、経路に沿った値の合計がtargetSumに等しい経路の数を返します。
経路は根や葉で始まる必要はありませんが、下方向（すなわち、親ノードから子ノードへのみ移動）でなければなりません。

素直に解いてみる

考え方

1. それぞれのパスの合計値を求める
2. targetSumとなる個数を数える

コーディング

function pathSum(root: TreeNode | null, targetSum: number): number {
    const func = (root: TreeNode | null, targetSum: number, sums: number[]): number => {
        if (!root) { return 0; }

        let match = 0;
        const newSums = [...sums, 0].map((sum) => {
            const newSum = sum + root.val;
            if (newSum === targetSum) { match++; }
            return newSum;
        });

        return func(root.left, targetSum, newSums) + func(root.right, targetSum, newSums) + match;
    }
    return func(root, targetSum, []);
};

結果

Runtime：119ms
Beats 17.96%

Memory：66.45MB
Beats 16.02%