-
814. Binary Tree Pruning(Python, LeetCode Medium)LeetCode 2022. 9. 6. 23:33
문제 설명
본인과 모든 자식 노드의 값이 0인 노드를 트리에서 제거합니다.
입력
root: 이진 트리의 루트 정점
풀이
이진 트리를 한 쪽씩 탐색합니다.
node의 left를 재귀적으로 탐색하여 모든 자식 노드의 값이 0이면 left 노드를 제거합니다.
node의 right를 재귀적으로 탐색하여 모든 자식 노드의 값이 0이면 right 노드를 제거합니다.
left와 right가 모두 None이면서 value가 0인 노드를 제거합니다.
코드
더보기* Solution Class를 제외한 코드는 Local Test를 위한 코드입니다.
from collections import deque from typing import Optional, List class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def __eq__(self, o: __build_class__) -> bool: return o and self.val == o.val and self.left == o.left and self.right == o.right def __str__(self) -> str: return f"val={{{self.val}}}, left={{{self.left}}}, right={{{self.right}}}" class Solution: def check_node(self, node: Optional[TreeNode]) -> bool: if not node: return False if not self.check_node(node.left): node.left = None if not self.check_node(node.right): node.right = None if not node.left and not node.right and not node.val: return False return True def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not self.check_node(root): return None return root def make_tree(root: List[int | None]) -> Optional[TreeNode]: root = deque(root) root_node = None queue = deque() while root: if root_node is None: root_node = TreeNode(root.popleft()) queue.append(root_node) else: node = queue.popleft() if root[0] is not None: next_node = TreeNode(root.popleft()) node.left = next_node queue.append(next_node) else: root.popleft() if root and root[0] is not None: next_node = TreeNode(root.popleft()) node.right = next_node queue.append(next_node) elif root: root.popleft() return root_node if __name__ == '__main__': solution = Solution() result = solution.pruneTree(make_tree(root=[1, None, 0, 0, 1])) print(make_tree([1, None, 0, None, 1]) == result, result) result = solution.pruneTree(make_tree(root=[1, 0, 1, 0, 0, 0, 1])) print(make_tree([1, None, 1, None, 1]) == result, result) result = solution.pruneTree(make_tree(root=[1, 1, 0, 1, 1, 0, 1, 0])) print(make_tree([1, 1, 0, 1, 1, None, 1]) == result, result)
'LeetCode' 카테고리의 다른 글
(임시) 967. Numbers With Same Consecutive Differences(Python, LeetCode Medium) (0) 2022.09.08 (임시)94. Binary Tree Inorder Traversal(Python, LeetCode Easy) (0) 2022.09.08 606. Construct String from Binary Tree(Python, LeetCode Easy) (0) 2022.09.07 429. N-ary Tree Level Order Traversal(Python, LeetCode Medium) (0) 2022.09.06 518. Coin Change 2(Python, LeetCode Medium) (0) 2022.09.04