129. Sum Root to Leaf Numbers

문제

Linked List 로 구현된 이진 트리가 주어졌을때, 루트 노드 부터 리프 노드까지 순회하면서 전체 노드의

총 합을 구하는 문제입니다.

 

그런데 아래 그림에 나온 설명처럼,

루트노드 부터 리프노드 까지의 숫자를 단순히 sum 하는것이 아닌 string 형태로 합친 후 sum 을 해야합니다.

 

문제 풀이

미디엄 문제 치고는 간단한 문제입니다.

전체 노드를 전위순회(pre order) 하기만 하면서 sum 을 해주면 풀립니다.

 

문제 풀이 코드

static int sum = 0;

public static int sumNumbers(TreeNode root) {
    preorder(root, "");
    return sum;
}

private static void preorder(TreeNode root, String num) {
    if(root == null) return;

    if(root.left == null && root.right == null) {
        sum += Integer.parseInt(num + root.val);
        return;
    }

    preorder(root.left, num + root.val);
    preorder(root.right, num + root.val);
}

 

1. 베이스 조건은 root 노드가 null 인 경우 입니다.

2. 루트노드의 왼쪽, 오른쪽 자식 노드가 모두 null 이면 리프노드이기 때문에 sum 을 해줍니다.

3. 왼쪽, 오른쪽 자식 노드 중 null 이 아닌 노드가 있다면 노드의 값을 + 해주면서 전위순회를 계속 해줍니다.

 

위 문제 풀이 코드는 String 으로 받아서 처리하도록 했습니다.

위와 같이 하지 않고 각 num 에 *10 을 붙여서 처리해도 됩니다.

 

예를들어, num 을 int 형으로 변환해주고 + 하는 시점에 아래와 같이 처리하면 됩니다.

num + root.val; 코드를 다음과 같이 변환해주면 굳이 String 으로 받지 않아도 됩니다.

sum += num * 10 + root.val;