[LeetCode] 623 | Add One Row to Tree | Python

---

문제 링크: https://leetcode.com/problems/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.

---

조건

• The number of nodes in the tree is in the range $[1, 10^4]$.
• The depth of the tree is in the range $[1, 10^4]$.
• -100 <= Node.val <= 100
• $-10^5$ <= val <= $10^5$
• 1 <= depth <= the depth of tree + 1

---

내 풀이

해당 depth에 val에 해당하는 새로운 노드를 추가한다는 뜻은, depth-1의 children 부분에 val에 해당하는 새로운 노드를 추가한다는 것이다.

그렇기 때문에 현재(node)의 깊이(d)가 depth-1이라면, node.left, node.right에 새로운 노드(newLeft, newRight)를 추가해주고, 기존의 node.left와 node.right를 각각 newLeft, newRight 아래에 둔다.

 

만약 depth가 1이라면 새로운 노드를 root로 만들고, 기존의 root를 newNode.left에 둔다.

---

코드

# 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]:
        def dfs(node, d):
            if not node:
                return
            
            if d == depth-1:
                newLeft = TreeNode(val, node.left)
                newRight = TreeNode(val, None, node.right)
                node.left = newLeft
                node.right = newRight
            else:
                dfs(node.left, d+1)
                dfs(node.right, d+1)
        
        if depth == 1:
            return TreeNode(val, root)
        else:
            dfs(root, 1)
        return root