112. Path Sum

주어진 이진 트리에서 루트부터 리프까지의 경로 중 합이 특정 값과 같은 경로가 있는지 확인하는 문제입니다. 간단히 말하면, 주어진 트리에서 어떤 경로를 따라 이동하면서 노드의 값을 더했을 때, 그 합이 주어진 값과 같은지를 확인하는 것입니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool HasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        if(root.val == targetSum && root.left == null && root.right == null) return true;
        return HasPathSum(root.left,targetSum-root.val) || HasPathSum(root.right,targetSum-root.val);
    }
}

 

주어진 이진 트리를 재귀적으로 탐색하면서 노드의 값을 더해가며 targetSum과 비교하면 됩니다. 루트부터 리프까지의 경로를 따라가면서 합이 targetSum과 같은 경우 true를 반환하고, 그렇지 않은 경우 false를 반환하면 됩니다.

주어진 트리가 빈 트리인 경우에는 false를 반환하고, 루트 노드의 값이 targetSum과 같고 자식이 없는 경우에는 true를 반환합니다. 그 외의 경우에는 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 탐색하면서 합이 targetSum과 같은 경로가 있는지 확인합니다.