# 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, val, depth):
if depth == 1:
new_root = TreeNode(val)
new_root.left = root
return new_root
def dfs(node, current_depth):
if not node:
return
if current_depth == depth - 1:
old_left = node.left
old_right = node.right
node.left = TreeNode(val)
node.left.left = old_left
node.right = TreeNode(val)
node.right.right = old_right
else:
dfs(node.left, current_depth + 1)
dfs(node.right, current_depth + 1)
dfs(root, 1)
return root
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* 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) {
TreeNode* newRoot = new TreeNode(val);
newRoot->left = root;
return newRoot;
}
dfs(root, val, 1, depth);
return root;
}
void dfs(TreeNode* node, int val, int current_depth, int target_depth) {
if (!node) return;
if (current_depth == target_depth - 1) {
TreeNode* oldLeft = node->left;
TreeNode* oldRight = node->right;
node->left = new TreeNode(val);
node->left->left = oldLeft;
node->right = new TreeNode(val);
node->right->right = oldRight;
} else {
dfs(node->left, val, current_depth + 1, target_depth);
dfs(node->right, val, current_depth + 1, target_depth);
}
}
};
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
if (depth == 1) {
TreeNode newRoot = new TreeNode(val);
newRoot.left = root;
return newRoot;
}
dfs(root, val, 1, depth);
return root;
}
private void dfs(TreeNode node, int val, int currentDepth, int targetDepth) {
if (node == null) return;
if (currentDepth == targetDepth - 1) {
TreeNode oldLeft = node.left;
TreeNode oldRight = node.right;
node.left = new TreeNode(val);
node.left.left = oldLeft;
node.right = new TreeNode(val);
node.right.right = oldRight;
} else {
dfs(node.left, val, currentDepth + 1, targetDepth);
dfs(node.right, val, currentDepth + 1, targetDepth);
}
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} val
* @param {number} depth
* @return {TreeNode}
*/
var addOneRow = function(root, val, depth) {
if (depth === 1) {
let newRoot = new TreeNode(val);
newRoot.left = root;
return newRoot;
}
function dfs(node, currentDepth) {
if (!node) return;
if (currentDepth === depth - 1) {
let oldLeft = node.left;
let oldRight = node.right;
node.left = new TreeNode(val);
node.left.left = oldLeft;
node.right = new TreeNode(val);
node.right.right = oldRight;
} else {
dfs(node.left, currentDepth + 1);
dfs(node.right, currentDepth + 1);
}
}
dfs(root, 1);
return root;
};
You are given the root of a binary tree, an integer val, and an integer depth. Your task is to add a new row of nodes with value val at the given depth in the tree.
depth == 1, you should create a new root node with value val and the original tree becomes its left subtree.depth - 1, insert two new nodes with value val as their left and right children. The original left child becomes the left child of the new left node, and the original right child becomes the right child of the new right node.Constraints:
To solve this problem, we first need to understand how tree depth works and how to traverse a tree to the correct level. The brute-force idea might be to traverse every node and check if it's at the required level, but this is inefficient and unnecessary. Instead, we can use a recursive or iterative approach to reach exactly the nodes at depth - 1, where we need to insert the new row.
The main challenge is handling the special case when depth == 1, which requires creating a new root. For other cases, we need to carefully rewire the tree so that the original children are attached to the new nodes, without losing any part of the tree.
The optimized approach is to use either Depth-First Search (DFS) or Breadth-First Search (BFS) to reach the target depth efficiently, then insert the new nodes as specified.
depth == 1. If so, create a new root node with value val, set the original root as its left child, and return the new root.depth - 1. This can be done recursively (DFS) or iteratively (BFS).depth - 1:
val as the left child. The original left child becomes the left child of this new node.val as the right child. The original right child becomes the right child of this new node.
We use recursion for simplicity and clarity. At each recursive call, we track the current depth. When we reach depth - 1, we insert the new nodes as described. This approach ensures that all insertions are done in-place and only at the correct depth.
Suppose the input is:
[4,2,6,3,1,5] (which looks like this:)
4
/ \
2 6
/ \ /
3 1 5
val = 1depth = 2depth != 1, we search for all nodes at depth 1 (the root in this case).4 (depth 1), we insert new nodes with value 1 as its left and right children.
4
/ \
1 1
/ \
2 6
/ \ /
3 1 5
This step-by-step insertion maintains the tree structure and adds the new row at the correct depth.
O(N) time and space, where N is the number of nodes.O(N). The space complexity is O(H) for recursion stack (where H is the tree height), or O(W) if using a queue for BFS (where W is the maximum width of the tree).The algorithm is efficient because it only modifies the necessary nodes and uses a single traversal.
The key insight is to traverse the tree to just before the target depth and insert new nodes without losing any of the original structure. Handling the edge case where the new row is added at the root is crucial. Using recursion or iteration, we can efficiently solve the problem in linear time, making this a clean and elegant solution for modifying binary trees.