Scribbling

O(N) 메모리를 사용한다면 매우 쉬운 문제이지만, 아래 Follow-up을 반영하여 O(1) 메모리를 사용하여 푸는 것은 조금 생각이 필요하다. Constant Memory로 어찌 풀지 생각하다가 아래 조건에서 힌트를 얻었다. Node의 개수에 제한이 있다는 것. Perfect Binary Tree에서 이와 같은 조건은 곧 최대 높이로 직결된다. 이를 활용하면, 트리의 층마다 last node 주소를 저장해놓고 갱신하는 방식으로 풀 수 있다. """ # Definition for a Node. class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val..

현재 node -> Flattened Left Tree -> Flattened Right Tree # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ if not root: return None head, tail = self.helpe..

1. 완전탐색 완전탐색으로 짜잔하고 풀리면 hard일리가 없지. 역시 Time Out class Solution: def numDistinct(self, s: str, t: str) -> int: self.answer = 0 self.dfs(s, t) return self.answer def dfs(self, s, t): if not t: self.answer += 1 return target = t[0] for i, char in enumerate(s): if char == target: self.dfs(s[i+1:], t[1:]) 2. DP 문자열을 탐색 혹은 비교하는 문제는 대부분 DP인 경우가 많다. 말그대로 dp다. 문제는 이것도 Time Out class Solution: def numDist..

DFS Solution # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]: if not root: return [] self.ret = [] self.dfs(root, [], 0, targetSum) return self.ret def dfs(self, node, path, tempSum, targ..

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]: if not head:..

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: return self.builder(inorder, postorder) def builder(self, inorder, postorder): if not inorder: return None head = TreeNode(val=postor..

재귀로 풀어주자 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: return self.builder(preorder, inorder) def builder(self, preorder, inorder): if not preorder: return None head = TreeNode(val..

102번 문제를 풀면 하나 더 주는 공짜 문제. 밑의 코드만 추가해준다. for i in range(len(ret)): if i % 2 == 1: ret[i].reverse() https://focalpoint.tistory.com/128 LeetCode: 102. Binary Tree Level Order Traversal - 시바견의 끄적임 BFS하면서 기록해준다. from collections import deque # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # s.. focalpoint...

BFS하면서 기록해준다. from collections import deque # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: return [] ret = [] q = deque() q.append((root, 0)) while q: cur_node, cur_level = q.popleft() ..

class Solution: def numTrees(self, n: int) -> int: dp = [0] * (n+1) dp[0] = 1 dp[1] = 1 for i in range(2, n+1): count = 0 for j in range(1, i+1): count += dp[j-1] * dp[i-j] dp[i] = count return dp[n]