Path Sum (Recursive)

LeetCode의 Binary Tree 튜토리얼 두 번째 섹션의 마지막 문제인 Path Sum이다.

Account Login - LeetCode

트리의 루트 노드부터 자식 노드까지 탐색하면서 한 경로의 노드 값들을 합해서 특정 값을 만들 수 있는지 확인하는 문제다. 노드의 값과 합해서 만들어야 하는 값들은 음수 또는 양수 둘 다 될 수 있기 때문에 말단 노드까지 합해가면서 특정 값이 만들어졌는지 확인해야 한다. 그래서 재귀적으로 이를 합산하려면 현재 노드까지의 합산 값을 매개변수로 하여 현재 노드의 왼쪽 노드와 오른쪽 노드를 매개변수로 넘겨서 탐색하는 재귀 함수를 작성할 필요가 있다.

 

이때 중요한 것은 루트 노드부터 말단 노드까지 경로상의 모든 노드의 값들을 합해서 판단해야 한다는 것이다. 그렇기 때문에 자식 노드가 둘 다 없는 말단 노드일 경우에만 현재 노드까지의 합을 기반으로 판단해야 한다. 말단 노드가 아닌 경우 계속 탐색해야 한다.

 

그리고 문제에서는 값을 만들 수 있는지 여부만을 판단하고 있기 때문에 다른 경로에서 특정 값을 만들었다면 더 탐색할 필요 없이 그대로 탐색을 종료하도록 최적화하는 방안을 생각해볼 수 있다. 알고리즘과 구현 자체는 그리 어렵지 않으며 이를 기반으로 작성한 코드는 다음과 같다.

class Solution {
    
    private boolean isPathEqual = false;
    
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        
        findPathSum(root, root.val, targetSum);
        return isPathEqual;
    }
    
    private void findPathSum(TreeNode root, int accumulateSum, int targetSum){
        if(isPathEqual) return;
        
        if(root.left == null && root.right == null && accumulateSum == targetSum){
            isPathEqual = true;
        }
        
        if(root.left != null){
            findPathSum(root.left, accumulateSum + root.left.val, targetSum);
        }
        if(root.right != null){
            findPathSum(root.right, accumulateSum + root.right.val, targetSum);
        }
    }
}

외부에 따로 boolean 변수를 유지하고 있는 것이 번거롭기 때문에 다른 풀이를 찾아보니 다음처럼 풀이 메서드 자체를 재귀 호출하는 것을 볼 수 있다.

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        int newSum = targetSum-root.val;

        if(newSum==0 && root.left == null && root.right == null){
            return true;
        }
        boolean leftPath = hasPathSum(root.left, newSum);
        boolean rightPath = hasPathSum(root.right, newSum);
        
        return leftPath||rightPath;
    }
}

시스템 스택에 현재 트리를 참조하는 노드도 같이 전달되기 때문에 이 문제 메서드 자체를 재귀 호출해도 문제가 없다. 대신 현재 노드까지의 합을 따로 전달할 수 없기 때문에 targetSum 매개변수를 감소시키면서 재귀 호출하는 것을 볼 수 있다.