623. Add One Row to Tree

문제

Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth.

Note that the root node is at depth 1.

The adding rule is:

-Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur's left subtree root and right subtree root.
-cur's original left subtree should be the left subtree of the new left subtree root.
-cur's original right subtree should be the right subtree of the new right subtree root.
-If depth == 1 that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root's left subtree.

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

접근

#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]:
        
        if depth == 1:
            return TreeNode(val, root, None) # 예외처리
        
        q = collections.deque([root]) # bfs를 위한 큐 선언. 앞뒤로 자료를 넣고 뺄 수 있다.
        
        while depth != 1:
            depth -= 1 # 목표depth까지 진행
            size = len(q) # n번째 깊이의 노드들을 전부 선택.
            
            for _ in range(size):
                node = q.popleft()
                l, r = node.left, node.right
                
                if depth == 1: #목표 깊이에 도달했으면
                    node.left = TreeNode(val, l, None)
                    node.right = TreeNode(val, None, r)
                    #노드 추가
                    continue
                if l:
                    q.append(l)
                if r:
                    q.append(r) #자식 노드를 큐에 추가
        return root
        

효율성

Runtime: 117 ms, faster than 22.42% of Python3 online submissions for Add One Row to Tree.
Memory Usage: 16.8 MB, less than 69.24% of Python3 online submissions for Add One Row to Tree.