Leetcode 623 . Add one Row to Tree (Binary tree)

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

Add One Row to Tree - LeetCode

 

---

정해진 depth 까지 도달했을 때, 주어진 val을 왼쪽과 오른쪽 노드로 삽입하고 기존의 왼쪽 노드는 새로운 노드의 왼쪽,

기존의 오른쪽 노드는 새로운 노드의 오른쪽으로 재배열 하는 문제입니다.

 

제가 처음에 접근했던 방식은 BFS로 stack을 통해 아래 로직을 전개하는걸로 생각했습니다.

1. depth 도달할 때까지 노드 순환

2. depth 도달 시에 새로운 노드 insert  및 기존 node.left와 node.right 를 한칸씩 left, right으로 밀기

3. Tree 재순회

 

하지만, insert기능을 따로 구현하고 재순회시키는 과정에서 애를 먹어서 다른 코드 분석을 진행해봤습니다.

 

---

Short BFS 풀이)

 

Leetcode 풀이에서 항상 상위권인 stefanPochmann 의 풀이입니다.

 

깔끔하게 앞에 for문에서 d-1의 깊이까지 탐색을 마치고

row에서 node를 가지고 와서 node.left = TreeNode(v) 로 v값을 node에 넣어주고

기존의 node.left는 node.left.left값에 넣어주었습니다

 

def addOneRow(self, root, v, d):
    dummy, dummy.left = TreeNode(None), root
    row = [dummy]
    for _ in range(d - 1):
        row = [kid for node in row for kid in (node.left, node.right) if kid]
    for node in row:
        node.left, node.left.left = TreeNode(v), node.left
        node.right, node.right.right = TreeNode(v), node.right
    return dummy.left

 

 

 BFS 풀이)

class Solution(object):
    def addOneRow(self, root, v, d):
        if d == 1:
            return TreeNode(v, root, None)
        
        bfs = deque([root])
        while bfs and d != 1:
            size = len(bfs)
            d -= 1
            for _ in range(size):
                curr = bfs.popleft()
                if curr.left != None:
                    bfs.append(curr.left)
                if curr.right != None:
                    bfs.append(curr.right)
                
                if d == 1: 
                    curr.left = TreeNode(v, curr.left, None)
                    curr.right = TreeNode(v, None, curr.right)
        return root

if 조건문을 통해 경우의 수를 분류해주고 마지막에 root가 반환되도록 했습니다

 

DFS 풀이)

class Solution(object):
    def addOneRow(self, root, v, d):
        if not root or d <= 0 : return None
        if d == 1:
            return TreeNode(v, root, None)
        if d == 2:
            root.left = TreeNode(v, root.left, None)
            root.right = TreeNode(v, None, root.right)
        else:
            root.left == self.addOneRow(root.left, v, d - 1)
            root.right == self.addOneRow(root.right, v, d - 1)
        return root

 

 

depth  직전 -> d==1이 아닐때 즉 d==2일 때 한칸씩 왼쪽 오른쪽으로 밀어주고

else의 경우에는 depth가 될 때까지 -1을 해주는 식으로 구성했습니다.