[leetcode] Sum Root to Leaf Numbers

문제

• 문제 링크
• [0, 9] 범위의 값을 갖는 이진 트리 root가 주어진다. 트리에서 각 root-to-leaf 경로는 숫자를 나타낸다. 예를 들어 root-to-leaf 경로가 1 -> 2 -> 3이면 123이라는 숫자로 나타낼 수 있다. 주어진 이진 트리 root에 존재하는 root-to-leaf의 총합을 구해야 한다. 테스트케이스는 정답이 32-bit 정수 안에 있도록 생성된다.
• 제약 조건
  • 트리에 있는 노드 개수: [1, 1000]
  • 노드 값 범위: 0 <= Node.val <= 9
  • 트리의 깊이는 10을 넘지 않음

풀이

풀기 전

• 트리 순회하다가 leaf 노드 만났을 때 숫자를 정답에 더해주면 된다.

코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
	// 현재 순회 중인 노드와 현재까지 오면서 더한 합을 파라미터로 갖는다.
    private int traverse(TreeNode node, int sum) {
        if (node == null)
            return 0;

        sum = sum * 10 + node.val;  // 현재 노드를 합에 더해준다.
        
        // 만약 leaf 노드이면 합을 반환한다.
        if (node.left == null && node.right == null) {
            return sum;
        }

		// 왼쪽 자식 노드와 오른쪽 자식 노드를 순회한다.
        return traverse(node.left, sum) + traverse(node.right, sum);
    }

    public int sumNumbers(TreeNode root) {
        return traverse(root, 0);
    }
}

푼 후

• 총 노드 개수를 n이라고 하면, 노드 개수만큼 순회하므로 시간 복잡도는 O(n)이다.
• 재귀 함수의 공간 복잡도는 보통 재귀 깊이로 생각할 수 있다. 해당 문제에서 재귀 깊이는 트리의 깊이와 동일하기 때문에 트리 깊이를 h라고 하면 공간 복잡도는 O(h)이다.