101. Symmetric Tree
https://leetcode.com/problems/symmetric-tree/
My Answer 1: Accepted (Runtime: 40 ms - 18.26% / Memory Usage: 14.4 MB - 51.19%)
# 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 isSymmetric(self, root: TreeNode) -> bool:
queue = [root.left]
left = []
while queue:
r = queue.pop(0)
if r:
queue.append(r.left)
queue.append(r.right)
left.append(r.val)
else:
left.append(-101)
queue = [root.right]
right = []
while queue:
r = queue.pop(0)
if r:
queue.append(r.right)
queue.append(r.left)
right.append(r.val)
else:
right.append(-101)
if left != right:
return False
return True루트의 left 와 right 를 나눠서
left 는 left -> right 순으로 보면서 value 를 left 에 저장
right 는 right -> left 순으로 보면서 value 를 right 에 저장
이 때, None 값도 처리를 해줘야 대칭인지 판별 가능 (값이 겹치는 경우도 있어서..)
둘이 같으면 True 다르면 False
My Answer 2: Accepted (Runtime: 36 ms - 58.21% / Memory Usage: 14.4 MB - 51.19%)
# 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 isSymmetric(self, root: TreeNode) -> bool:
def func(left, right):
if left is None and right is None:
return True
if left is None or right is None or left.val != right.val:
return False
ans = True
ans &= func(left.left, right.right)
ans &= func(left.right, right.left)
return ans
return func(root.left, root.right)Follow up: Could you solve it both recursively and iteratively?
시간 여유가 있어서 재귀로도 풀어봄
func(root.left, root.right) => 루트의 left 와 right 를 동시에 확인
(left.left, right.right) & (left.right, right.left)
서로 대칭이 되는 애들끼리 다음 값으로 넘겨줌
left, right 가 서로 값이 같아서 무난히 통과하다 둘 다 None 이 되면 True
둘 중 하나만 None 이거나 둘의 값이 다르면 대칭이 아니므로 False
Solution 1: Accepted (Runtime: 32 ms - 81.99% / Memory Usage: 14.4 MB - 51.19%)
# 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 isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
# root의 left, right를 넣기
queue = [(root.left, root.right)]
while queue:
# left는 l로, right는 r로 pop
l,r = queue.pop()
# 둘 다 null 이면 같으니까 continue
if not l and not r:
continue
# 둘 중에 하나만 null 이면 다르니까 False
if not l or not r:
return False
# 둘이 값이 다르면 False
if l.val != r.val:
return False
# 대칭이어야 하는 애들끼리 append
queue.append((l.left, r.right))
queue.append((r.left, l.right))
return True재귀처럼 left 와 right 를 한번에 보는 방식
확실히 루션이가 깔끔하네요^^
104. Maximum Depth of Binary Tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/
My Answer 1: Accepted (Runtime: 44 ms - 47.32% / Memory Usage: 16.4 MB - 14.31%)
# 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 maxDepth(self, root: TreeNode) -> int:
def func(root, cnt):
if root is None:
self.ans = max(self.ans, cnt)
return
func(root.left, cnt+1)
func(root.right, cnt+1)
self.ans = 0
func(root, 0)
return self.ansDFS 로 보면서 깊이 count 해줌
끝까지 가면 self.ans 를 최댓값으로 update
My Answer 2: Accepted (Runtime: 40 ms - 75.11% / Memory Usage: 15.3 MB - 96.41%)
# 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 maxDepth(self, root: TreeNode) -> int:
if root is None:
return 0
queue = [root]
ans = 0
while queue:
for i in range(len(queue)):
r = queue.pop(0)
if r:
if r.left:
queue.append(r.left)
if r.right:
queue.append(r.right)
ans += 1
return ans이 문제도 시간 여유가 돼서 반복문으로도 풀어봄
level-order 로 보면서 level 을 계산해줌
for 문에서 한 레벨의 모든 값들 처리
Solution 1: Accepted (Runtime: 44 ms - 47.32% / Memory Usage: 16.1 MB - 62.40%)
# 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 maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))초간단 루션이
46. Permutations
https://leetcode.com/problems/permutations/
My Answer 1: Accepted (Runtime: 36 ms - 88.69% / Memory Usage: 14.4 MB - 43.71%)
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def permutation(nums, p):
if len(nums) == 0:
self.ans.append(p)
return
for i in range(len(nums)):
permutation(nums[:i]+nums[i+1:], p+[nums[i]])
self.ans = []
permutation(nums, [])
return self.ans재귀로 조합 찾아주기
nums 의 각 숫자 하나만 떼다가 p 에 붙여주기
48. Rotate Image
https://leetcode.com/problems/rotate-image/
My Answer 1: Accepted (Runtime: 36 ms - 63.40% / Memory Usage: 14.4 MB - 5.44%)
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
m = len(matrix)
n = len(matrix[0])
for i in range(m):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(m):
matrix[i].reverse()[0,0] [0,1] [0,2] [2,0] [1,0] [0,0] [1,0] [1,1] [1,2] => [2,1] [1,1] [0,1] [2,0] [2,1] [2,2] [2,2] [1,2] [0,2]rotate 전후의 행렬 인덱스 변화
추가 배열 없이 주어진 matrix 만 사용해서 풀어야한대서..
규칙을 찾으려고 써봤더니 i <-> j & reverse 하는게 보임
[0,0], [1,1], [2,2], ... 부터 보면서 matrix[i][j] <-> matrix[j][i] 해주고
각 row reverse() 하면 끝~~
