[알고리즘] Binary Tree Pruning

포인트

• Pruning 가지치기를 뜻하면 백트랙킹에서 사용하는 단어 입니다. 이 문제에서는 0을 가지고 있는 것을 왼쪽 노드와 오른쪽 노드가 None 인 것을 찾는 문제 입니다. 
• 재귀적인 방법으로 탐색하여 처리하는 문제 입니다. 트리를 탐색하는 방법 중 후위 탐색과 비슷한 모양입니다. 참고하시면 좋을 것 같습니다. 

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

트리 순회 - 위키백과, 우리 모두의 백과사전

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            # 루트가 None 이면 None 을 반환
            return None

        root.left = self.pruneTree(root.left)
        # 왼쪽으로 들어가면서 탐색
        root.right = self.pruneTree(root.right)
        # 오른쪽으로 들어가면서 탐색
        if root.val == 0 and root.left is None and root.right is None:
            # 값이 0이고 왼쪽과 오른쪽 모두 None 이면 None 을 반환
            return None
        return root        
        # 아니면 root를 반환