C#で二分木に指定した合計値となるパスが存在するか判定する方法

二分木において、ルートから葉までの経路（パス）上のノード値の合計が、指定された値と一致するかどうかを判定する問題は、木構造のアルゴリズム学習における定番テーマの一つです。この記事では、C#を使ってこの問題を再帰的に解く方法を解説します。

アルゴリズムの考え方

HasPathSum メソッドは、2つの引数を受け取ります。1つ目は木のノード、2つ目は目標となる合計値です。

処理の流れは以下のとおりです。

1. 最初にノードが null かどうかをチェックします。ノードが null の場合は false を返します。
2. ノードが null でなければ、再帰メソッド helperHasPathSum を呼び出します。
3. 再帰の各ステップでは、現在のノードの値を合計値から引き算していきます。
4. 葉ノード（左右の子を持たないノード）に到達した時点で合計値がちょうど 0 になっていれば、「指定された合計値に等しいパスが存在する」と判断し、true を返します。

このように「残りの合計値」を親から子へ渡しながら減算していくことで、各パスの合計が目標値と一致するかを効率的に判定できます。

実装例

public class TreesPgm{
    public class Node{
        public int Value;
        public Node LeftChild;
        public Node RightChild;
        public Node(int value){
            this.Value = value;
        }
        public override String ToString(){
            return "Node=" + Value;
        }
    }
    public bool HasPathSum(Node node, int sum){
        if (node == null){
            return false;
        }
        return helperHasPathSum(node, sum);
    }
    private bool helperHasPathSum(Node root, int sum){
        if (root == null){
            return false;
        }
        sum -= root.Value;
        if (root.LeftChild == null && root.RightChild == null && sum == 0){
            return true;
        }
        return helperHasPathSum(root.LeftChild, sum) || helperHasPathSum(root.RightChild, sum);
    }
}

ポイントとして、公開メソッド HasPathSum で null チェックを行い、実際の再帰処理はプライベートメソッド helperHasPathSum に分離しています。これによりコードの責務が明確になり、可読性が向上します。また、葉ノードの判定を root.LeftChild == null && root.RightChild == null で行うことで、途中のノードで合計が 0 になっても誤って true を返さないようになっています。

入力例

          5
      2       6
   1     3
7

出力結果

True

この例では、たとえば「5 → 2 → 3」というパスの合計が 10 になるため、指定した合計値に一致するパスが存在することになり、結果は True となります。

計算量について

このアルゴリズムは各ノードを一度だけ訪問するため、時間計算量は O(n)（n はノード数）です。また、再帰呼び出しの深さは木の高さに依存するため、空間計算量は最悪の場合 O(n)、バランスの取れた木では O(log n) となります。