[leetcode] Sum of Left Leaves

문제

• 문제 링크
• 이진 트리인 root가 주어진다. 모든 left leaves의 합을 구해야 한다. leaf는 자식이 없는 노드를 의미한다. left leaf는 다른 노드의 왼쪽 자식인 leaf를 의미한다.
• 제약 조건
  • tree에 있는 노드 개수: [1, 1000]
  • 노드 값 범위: -1000 <= Node.val <= 1000

풀이

풀기 전

• 트리 탐색하면서 leaf 노드 중에서도 left 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 sumOfLeftLeaves;

	// 트리 탐색하는 함수이다.
    private void traverse(TreeNode node, boolean isLeft) {
        if (node == null)
            return;

		// Left leaf인지 체크한다.
        // isLeft가 true이면 부모 노드의 왼쪽 노드로 들어왔다는 의미이다.
        // left와 right가 모두 null이면 leaf 노드라는 의미이다.
        if (isLeft && node.left == null && node.right == null) {
            sumOfLeftLeaves += node.val;
            return;
        }

		// 왼쪽, 오른쪽 노드를 탐색한다.
        traverse(node.left, true);
        traverse(node.right, false);
    }

    public int sumOfLeftLeaves(TreeNode root) {
        sumOfLeftLeaves = 0;
        traverse(root, false);
        return sumOfLeftLeaves;
    }
}

푼 후

• 트리를 탐색할 줄 알면 풀 수 있는 문제였다.
• 노드의 총 개수를 n이라고 하면, n개의 노드를 한 번씩 순회하기 때문에 시간 복잡도는 O(n)이다.
• 재귀 함수의 공간 복잡도는 재귀 깊이로 생각할 수 있다. 해당 문제에서 재귀 깊이는 트리의 깊이와 동일하다. 트리의 깊이가 가장 깊은 경우는 모든 노드가 자식 하나만 가질 때이다. 그럼 한쪽으로 긴 트리가 만들어진다. 따라서 공간 복잡도는 O(n)이다.