> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/tree/623-add-one-row-to-tree.md).

# 623 Add One Row to Tree

## [623. Add One Row to Tree](https://leetcode.com/problems/add-one-row-to-tree/description/)

## 1. Question

Given the root of a binary tree, then value`v`and depth`d`, you need to add a row of nodes with value`v`at the given depth`d`. The root node is at depth 1.

The adding rule is: given a positive integer depth`d`, for each NOT null tree nodes`N`in depth`d-1`, create two tree nodes with value`v`as`N's`left subtree root and right subtree root. And`N's`**original left subtree** should be the left subtree of the new left subtree root, its **original right subtree** should be the right subtree of the new right subtree root. If depth`d`is 1 that means there is no depth d-1 at all, then create a tree node with value**v**as the new root of the whole original tree, and the original tree is the new root's left subtree.

**Example 1:**

```
Input:

A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   


v = 1
d = 2
Output:

       4
      / \
     1   1
    /     \
   2       6
  / \     / 
 3   1   5
```

**Example 2:**

```
Input:

A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    


v = 1
d = 3
Output:

      4
     /   
    2
   / \    
  1   1
 /     \  
3       1
```

**Note:**

1. The given d is in range \[1, maximum depth of the given tree + 1].
2. The given binary tree has at least one tree node.

## 2. Implementation

(1) BFS

```java
class Solution {
    public TreeNode addOneRow(TreeNode root, int v, int d) {
        if (root == null) {
            return root;
        }

        if (d == 1) {
            TreeNode newRoot = new TreeNode(v);
            newRoot.left = root;
            return newRoot;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int curDepth = 1, size = 0;
        boolean reach = false;

        while (!queue.isEmpty()) {
            size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.remove();
                TreeNode leftSubTree = curNode.left;
                TreeNode rightSubTree = curNode.right;

                if (d - 1 == curDepth) {
                    curNode.left = new TreeNode(v);
                    curNode.right = new TreeNode(v);
                    curNode.left.left = leftSubTree;
                    curNode.right.right = rightSubTree;
                    reach = true;
                }
                else {
                   if (leftSubTree != null) {
                       queue.add(leftSubTree);
                   }
                   if (rightSubTree != null) {
                       queue.add(rightSubTree);
                   } 
                }
            }
            if (reach) {
                break;
            }
            ++curDepth;
        }
        return root;
    }
}
```

(2) DFS

```java
class Solution {
    public TreeNode addOneRow(TreeNode root, int v, int d) {
        if (root == null) {
            return root;
        }

        if (d == 1) {
            TreeNode newRoot = new TreeNode(v);
            newRoot.left = root;
            return newRoot;
        }

        dfs(root, 1, v, d);
        return root;
    }

    public void dfs(TreeNode node, int depth, int v, int target) {
        if (node == null) {
            return;
        }

        if (depth == target - 1) {
            TreeNode leftSubTree = node.left;
            TreeNode rightSubTree = node.right;
            node.left = new TreeNode(v);
            node.right = new TreeNode(v);
            node.left.left = leftSubTree;
            node.right.right = rightSubTree;
            return;
        }

        dfs(node.left, depth + 1, v, target);
        dfs(node.right, depth + 1, v, target);
    }
}
```

## 3. Time & Space Complexity

BFS: 时间复杂度O(n), 空间复杂度: O(w)

DFS: 时间复杂度O(n), 空间复杂度: O(d), d是输入里的d