Sponsored
Sponsored
This approach uses recursion to traverse the tree to the right depth, modifying the tree structure as necessary to add the new row of nodes. We'll use a recursive helper function that takes the current node and the current depth as parameters. If the current depth is at depth - 1, we add new nodes with the given value as left and right children. If the current depth is less, we recursively call the helper function on the left and right children (if they exist).
The base case for this recursion is reaching a null node, where we simply return.
Time Complexity: O(n), because each node is visited exactly once.
Space Complexity: O(d), where d is the depth of the tree, due to the recursion stack.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7def addOneRow(root, val, depth):
8 if depth == 1:
9 return TreeNode(val, left=root)
10
11 def dfs(node, current_depth):
12 if not node:
13 return
14 if current_depth == depth - 1:
15 node.left = TreeNode(val, left=node.left)
16 node.right = TreeNode(val, right=node.right)
17 else:
18 dfs(node.left, current_depth + 1)
19 dfs(node.right, current_depth + 1)
20
21 dfs(root, 1)
22 return rootThis solution defines a TreeNode class for the tree nodes and a function addOneRow which is designed to modify the tree in place. It first checks if the depth is 1, which requires creating a new root node with the provided val and making the existing tree its left subtree. For deeper levels, it recursively traverses the tree using depth-first search, adding new nodes at the correct level.
This approach uses a breadth-first search (BFS) iteration over the tree. We can use a queue to traverse the tree level by level. At each level, if the current level is depth - 1, we add a new row of nodes. Otherwise, we queue the next level of nodes.
Time Complexity: O(n), since every node is considered once in the BFS loop.
Space Complexity: O(n), where n is the number of nodes at the breadth of the tree, due to the queue.
1import java.util.*;
2
3class TreeNode {
This approach involves using a queue to perform a level-order traversal of the tree. The objective is to reach nodes at depth depth-1 such that we can add new nodes with value val at the desired depth.
If the depth is 1, simply create a new root node with value val and make the original tree the left subtree of the new root.
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once.
Space Complexity: O(n) in the worst case to keep the queue, if the tree is a balanced tree, or O(h) where h is the height of the tree in a skewed tree.
1class TreeNode:
2 def
This approach uses a recursive depth-first search to traverse the tree. The function is designed to target depth depth-1 to manipulate and add the new nodes at the desired level.
An edge case at depth 1 involves creating a new root, similar to the BFS approach.
Time Complexity: O(n), where n is the total number of nodes in the tree, as each node is visited once.
Space Complexity: O(h) due to the recursive call stack, where h is the height of the tree.
1class TreeNode {
2public:
3 int val;
4 TreeNode* left;
5 TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int val, int depth) {
if (depth == 1) {
return new TreeNode(val, root, nullptr);
}
dfs(root, val, depth, 1);
return root;
}
void dfs(TreeNode* node, int val, int depth, int currentDepth) {
if (!node) return;
if (currentDepth == depth - 1) {
node->left = new TreeNode(val, node->left, nullptr);
node->right = new TreeNode(val, nullptr, node->right);
return;
}
dfs(node->left, val, depth, currentDepth + 1);
dfs(node->right, val, depth, currentDepth + 1);
}
};The solution involves creating a TreeNode class and a method that adds a row to the tree. If the depth is 1, a new root node is created with the current tree as its left child. For other depths, a queue is used to perform a level-order traversal until the level before the intended depth is reached. Then, new nodes with the given value are inserted as left and right children of the current nodes. The original children are reattached to the new nodes.
In this Python solution, a queue is used for breadth-first search (BFS) traversal. When the current depth equals depth-1, new nodes are inserted between the current nodes and their children, effectively at the specified depth. If the depth is 1, a new root is created with the existing root as its left child.
The C++ solution employs recursion to explore each depth level. The recursion continues to descend until reaching depth-1, where new nodes are created and attached. The solution gracefully handles the edge case of depth being 1 by creating a new root node.