릿코드
-
606. Construct String from Binary Tree(Python, LeetCode Easy)LeetCode 2022. 9. 7. 20:17
문제 설명 이진 트리의 각 요소들을 전위순회하며, 각 요소를 구분할 수 있도록 괄호로 감쌉니다. 입력 root: 이진 트리의 루트 정점 풀이 이진 트리를 한 쪽씩 탐색합니다. node.val를 출력하고, 좌측 노드가 반환하는 값을 괄호로 감싸 문자열에 더합니다. 우측 노드가 반환하는 값 또한 괄호로 감싸 문자열에 더합니다. 1:1 매핑 관계에 영향을 미치지 않는 빈 괄호 쌍은 생략한다는 규칙에 따라, 좌측 노드와 우측 노드 모두 존재하지 않는 경우는 빈 괄호쌍을 생략합니다. 좌측 노드만 있고 우측 노드는 없는 경우, 좌측 노드만 표시합니다. 좌측 노드는 없고 우측 노드만 있는 경우에는 1:1 매핑 관계를 유지해야 하기에 좌측의 빈 괄호를 유지합니다. 좌측 노드와 우측 노드 모두 존재하는 경우, 둘 다 표..
-
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,..
-
429. N-ary Tree Level Order Traversal(Python, LeetCode Medium)LeetCode 2022. 9. 6. 03:21
문제 설명 트리의 각 레벨 요소끼리 묶어 리스트를 만들어 반환합니다. 입력 root: 'Node': 트리의 루트 정점 풀이 트리를 가로(레벨별)로 순회하는 문제입니다. 루트로부터 시작하여 각 레벨을 탐색하며 결과를 종합하므로, 시작 정점인 루트를 큐에 담는 것으로 동작을 시작합니다. 다음 레벨의 노드를 담을 큐를 생성하고, 현재 큐에 담긴 노드를 순회하며 자식 노드를 다음 레벨 큐에 저장합니다. 동시에 현재 큐에 담긴 노드의 val을 결과 배열에 삽입합니다. 현재 큐가 순회를 마치면 다음 큐의 순회를 시작하기 위해 현재 큐에 대입합니다. 만약 어떤 노드도 자식 노드를 갖고 있지 않아 다음 큐가 비게 된다면, 모든 노드를 탐색한 것이므로 결과를 반환합니다. 코드 더보기 * Solution Class 이외 ..
-
518. Coin Change 2(Python, LeetCode Medium)LeetCode 2022. 9. 4. 22:49
문제 설명 주어진 동전을 이용하여 주어진 금액을 만드는 방법의 수를 반환하세요! 입력 coins: 동전의 종류를 의미하는 1차원 리스트 amount: 구성해야하는 총 금액 풀이 만약, [1, 2]원의 코인으로 3원을 만든다고 할 때, 1원은 0 → 1, 1 → 2, 2 → 3의 경우에 사용할 수 있으며, 2원은 0 → 2, 1 → 3의 경우에 사용할 수 있습니다. 동전을 하나씩 차례로 순회하며, 해당 동전의 크기만큼을 뺀 위치에 있는 숫자를 현재 위치에 더하는 방법으로 접근할 수 있습니다. 코드 더보기 from typing import List class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [0] * (amount..