leetcode medium : Add One Row to Tree

https://leetcode.com/problems/add-one-row-to-tree/

Add One Row to Tree - LeetCode

 

특정 레벨에 특정 값을 가지는 노드를 추가하는 문제

dfs로도 풀수있고 bfs로도 풀수있는데 난 bfs로 풀었고 코드가 좀 지저분해졌다.

# 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 addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
        dummy = TreeNode(val)
        dummy.left = root
        level = deque([dummy])
        
        if depth == 1:
            return dummy
        
        for _ in range(depth - 1):
            length = len(level)
            for i in range(length):
                if level[i]:
                    level.append(level[i].left)
                    level.append(level[i].right)
            for i in range(length):
                level.popleft()
                
        for node in level:
            if node:
                leftNode = TreeNode(val, node.left)
                rightNode = TreeNode(val, None, node.right)
                node.left = leftNode
                node.right = rightNode

        return root

메모리는 굳인데 시간이..ㅋㅋㅋㅋ 나 30년 전에 프로그래머였으면 메모리 꽤나 잘 아끼는 훌륭한 프로그래머였을지도..?ㅋㅋㅋㅋㅋ

 

# 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 addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
        dummy = TreeNode(val)
        dummy.left = root
        level = [dummy]
        
        if depth == 1:
            return dummy
        
        for _ in range(depth - 1):
            newlevel = []
            for node in level:
                if node:
                    newlevel.append(node.left)
                    newlevel.append(node.right)
            level = newlevel
                
        for node in level:
            if node:
                leftNode = TreeNode(val, node.left)
                rightNode = TreeNode(val, None, node.right)
                node.left = leftNode
                node.right = rightNode

        return root

중간에 deque 쓰는거 빼고 그냥 리스트 교체하는 로직으로 바꿨다.

메모리를 포기하고 시간을 좀더 살려살려