leetcode medium : Binary Tree Pruning

https://leetcode.com/problems/binary-tree-pruning/

Binary Tree Pruning - LeetCode

 

데일리 문제로 떠있었는데 정답률이 70프로길래 한번 풀어봤다.

 

재귀적으로 left subtree와 right subtree를 검사해서 1이 있으면 냅두고 아니면 삭제하고를 반복한다.

 

class Solution:
    def contain1(self, root):
        left1 = False
        right1 = False
        if root.left and self.contain1(root.left):
            left1 = True
        if root.right and self.contain1(root.right):
            right1 = True
        
        if not left1:
            root.left = None
        if not right1:
            root.right = None
            
        return left1 or right1 or root.val == 1
        
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if self.contain1(root):
            return root
        else:
            return None

 

처음으로 작성한 솔루션인데 통과는 했다.

트리 노드 개수가 N일때

시간복잡도는 O(N)이고 공간복잡도는 재귀함수때문에 평균 O(log N) ~ 최대 O(N)일거같다.

 

if문이 좀 많고 러프한 느낌이 있어서 살짝 다듬어봐야겠다

 

스터디 동료가 푼거

오 잘풀었다 헬퍼 메서드 없이 풀었네!! 잘풀었다!!!