-
606. Construct String from Binary Tree(Python, LeetCode Easy)LeetCode 2022. 9. 7. 20:17
문제 설명
이진 트리의 각 요소들을 전위순회하며, 각 요소를 구분할 수 있도록 괄호로 감쌉니다.
입력
root: 이진 트리의 루트 정점
풀이
이진 트리를 한 쪽씩 탐색합니다.
node.val를 출력하고, 좌측 노드가 반환하는 값을 괄호로 감싸 문자열에 더합니다.
우측 노드가 반환하는 값 또한 괄호로 감싸 문자열에 더합니다.
1:1 매핑 관계에 영향을 미치지 않는 빈 괄호 쌍은 생략한다는 규칙에 따라,
좌측 노드와 우측 노드 모두 존재하지 않는 경우는 빈 괄호쌍을 생략합니다.
좌측 노드만 있고 우측 노드는 없는 경우, 좌측 노드만 표시합니다.
좌측 노드는 없고 우측 노드만 있는 경우에는 1:1 매핑 관계를 유지해야 하기에 좌측의 빈 괄호를 유지합니다.
좌측 노드와 우측 노드 모두 존재하는 경우, 둘 다 표시합니다.
코드
더보기* 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 class Solution: def check_node(self, root: Optional[TreeNode]): part = "" if not root: return part part += str(root.val) if root.left or root.right: part += f"({self.check_node(root.left)})" if root.right: part += f"({self.check_node(root.right)})" return part def tree2str(self, root: Optional[TreeNode]) -> str: return self.check_node(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.tree2str(make_tree(root=[1, 2, 3, 4])) print("1(2(4))(3)" == result, result) result = solution.tree2str(make_tree(root=[1, 2, 3, None, 4])) print("1(2()(4))(3)" == 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 814. Binary Tree Pruning(Python, LeetCode Medium) (0) 2022.09.06 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