[LeetCode] 814. Binary Tree Pruning

문제

0과 1로만 이루어진 이진 트리에서, 1을 하나도 포함하지 않는 서브트리를 모두 제거한 트리를 반환한다.

접근

"0인 노드를 지운다"가 아니라 "1이 없는 서브트리를 지운다" 는 점이 핵심이다.
값이 0이어도 자손에 1이 있으면 그 노드는 남아야 한다.

노드를 지울지는 자식들의 결과를 알아야 정할 수 있으므로, 자식부터 처리하는 후위 순회(post-order)로 푼다.

1. 왼쪽, 오른쪽 서브트리를 먼저 가지치기한다.
2. 가지치기 후 자식이 둘 다 null이면 아래쪽에 1이 없다는 뜻이다.
3. 이때 자신의 값도 0이면 null을 반환해 자신을 제거한다.

코드

function pruneTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;

    root.left = pruneTree(root.left);
    root.right = pruneTree(root.right);

    if (root.val === 0 && !root.left && !root.right) return null;
    return root;
}

복잡도

• 시간: O(n), 모든 노드를 한 번씩 방문한다.
• 공간: O(h), 재귀 호출 스택이 트리 높이만큼 쌓인다.

정리

• 부모의 판단이 자식의 결과에 의존하면 후위 순회를 떠올린다.
• 재귀 결과를 root.left, root.right에 다시 대입하면 별도의 삭제 로직 없이 가지치기가 끝난다.
• 트리 전체가 0이면 루트도 제거되어 null이 반환된다.