# 資訊

:::info
- Question: 623. Add One Row to Tree
- From: Leetcode Daily Challenge 2024.04.16
- Difficulty: Medium
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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.

> Example 1:
:::success
* Input: `root = [4,2,6,3,1,5]`, `val = 1`, `depth = 2`
* Output: `[4,1,1,2,null,null,6,3,1,5]`
:::

> Example 2:
:::success
* Input: `root = [4,2,null,3,1]`, `val = 1`, `depth = 3`
* Output: `[4,2,null,1,1,3,null,null,1]`
:::

> Constraints:
:::success
* 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
:::

---

# 解法

## 概念

這題要加一層 nodes，原本以為要刻 BFS 了，後面想想，把深度帶進去就可以用 DFS 走完，而且還滿快的！

不過小例外就是在 `depth = 1` 或 depth 會是最後一層的時候，這兩層要稍微注意一下就可以了

## 程式碼

# 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 __init__(self):
        self.depth = 0
        self.val = 0
    def dfs(self, root: TreeNode, d: int):
        if d == self.depth - 1:
            L = TreeNode(val = self.val, left = root.left, right = None)
            root.left = L
            R = TreeNode(val = self.val, left = None, right = root.right)
            root.right = R
            d += 1
        # Traverse left
        if root.left:
            self.dfs(root.left, d+1)
        # Traverse right
        if root.right:
            self.dfs(root.right, d+1)
        return
    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
        self.depth = depth
        self.val = val
        if depth == 1:
            L = TreeNode(val=self.val, left=root, right=None)
            L.left = root
            return L
        else:
            self.dfs(root, 1)
        return root

---

# 複雜度

## 時間複雜度

走完所有 tree nodes，所以是 $O(n)$


## 空間複雜度

空間沒什麼額外宣告的部分，除了多的 tree nodes，但那些是答案的一部分，所以也不算，因此是 $O(1)$