C#으로 이진 트리에서 주어진 경로 합이 존재하는지 확인하는 방법

이진 트리에서 루트 노드부터 리프 노드까지 이어지는 경로를 따라 노드 값들을 모두 더했을 때, 그 합이 목표값과 정확히 일치하는 경로가 존재하는지 확인하는 것은 자주 등장하는 대표적인 트리 탐색 문제입니다. C#에서는 재귀(Recursion)를 활용하면 간결하고 효율적으로 해결할 수 있습니다.

동작 원리

HasPathSum 메서드는 두 개의 매개변수를 받습니다. 하나는 트리의 노드이고, 다른 하나는 찾고자 하는 합(sum)입니다. 먼저 해당 노드가 null인지 검사하여, null이라면 false를 반환합니다. 노드가 null이 아니라면 재귀 헬퍼 메서드(helperHasPathSum)를 호출합니다.

재귀 호출이 진행되는 매 단계마다 현재 노드의 값을 sum에서 차감합니다. 리프 노드(자식이 없는 노드)에 도달했을 때 sum이 정확히 0이 된다면, 루트부터 해당 리프까지의 경로 합이 목표값과 일치한다는 의미이므로 true를 반환합니다. 왼쪽 또는 오른쪽 자식 중 어느 한쪽이라도 조건을 만족하는 경로를 찾으면 전체 결과는 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);
    }
}

입력 트리

          5
      2       6
   1     3
7

위 트리에서 루트(5)부터 리프(7)까지의 경로는 5 → 2 → 1 → 7이며, 이 경로의 합은 15입니다. 만약 sum으로 15를 전달하면 일치하는 경로가 존재하므로 결과는 true가 됩니다.

출력

True

정리

이 알고리즘은 깊이 우선 탐색(DFS) 방식으로 트리를 순회하며, 각 경로마다 남은 합을 추적합니다. 시간 복잡도는 O(n)(n은 노드 수), 공간 복잡도는 재귀 스택 깊이에 비례하여 최악의 경우 O(n)입니다. 균형 잡힌 트리라면 O(log n) 수준의 스택 공간만 사용합니다.