669. Trim a Binary Search Tree
Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer.
Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.
My Answer 1: Accepted (Runtime: 48 ms - 73.85% / Memory Usage: 18.2 MB - 73.96%)
# 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 trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
# left = 0, right = 1
def func(root, prev, lr):
if root is None:
return
if root.val == low:
root.left = None
if root.val == high:
root.right = None
if root.val >= low and root.val <= high:
if lr:
prev.right = root
else:
prev.left = root
func(root.left, root, 0)
func(root.right, root, 1)
if root.val > high:
func(root.left, prev, lr)
if root.val < low:
func(root.right, prev, lr)
tmp = TreeNode(0)
tmp.left = root
func(root, tmp, 0)
if tmp.left.val < low or tmp.left.val > high:
return None
return tmp.left이거 저번에 못 풀었던 걸로 기억하는데 이번엔 풀었다
우선 root 앞에 노드를 하나 더 추가해서 그 노드를 root 의 prev 노드로 설정
재귀 돌려서
val == low => 왼쪽 trim
val == high => 오른쪽 trim
low ~ high => lr 값을 기준으로 prev 와 연결
val < low => 작은 값은 볼 필요 없으므로 right 로
val < high => 큰 값은 볼 필요 없으므로 left 로
마지막은 모든 값이 low ~ high 에 포함되지 않을 경우 None return
Solution 1: Accepted (Runtime: 52 ms - 49.67% / Memory Usage: 18.2 MB - 53.61%)
# 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 trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
def trim(node):
if not node:
return None
elif node.val > high:
return trim(node.left)
elif node.val < low:
return trim(node.right)
else:
node.left = trim(node.left)
node.right = trim(node.right)
return node
return trim(root)루션이는 더 간단하다...
그냥 low ~ high 범위 안에 있는 값들은 node 를 return 하고 나머지는 None return
외워!!!!!!!!!!!
445. Add Two Numbers II
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
My Answer 1: Accepted (Runtime: 76 ms - 40.33% / Memory Usage: 14.2 MB - 90.16%)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
def func(l):
num = ""
while l:
num += str(l.val)
l = l.next
return int(num)
n1 = func(l1)
n2 = func(l2)
ans = str(n1 + n2)
result = ListNode(0)
head = result
while len(ans) != 0:
result.next = ListNode(int(ans[0]))
ans = ans[1:]
result = result.next
return head.next이 문제.. 본 적은 있지만 푼 적은 없는..
우선 l1 과 l2 를 숫자로 바꾸고 더해준 후 string 형태로 ans 에 저장
result 노드를 만들어서 ans[0] 의 값을 갖는 노드를 next 에 연결해줌 => 순서대로 연결
Solution 1: Accepted (Runtime: 68 ms - 84.88% / Memory Usage: 14.4 MB - 43.67%)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
stack1, stack2 = [], []
while l1:
stack1.append(l1.val)
l1 = l1.next
while l2:
stack2.append(l2.val)
l2 = l2.next
carry, head = 0, None
while stack1 or stack2 or carry:
d1 = stack1.pop() if stack1 else 0
d2 = stack2.pop() if stack2 else 0
carry, val = divmod(d1+d2+carry, 10)
head = ListNode(val, head)
return headstack 2 개를 사용해서 carry 값까지 고려하기
좀 더 빠르네요^^
0개의 댓글
