623. Add One Row to Tree
Medium
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 nodecurat the depthdepth - 1, create two tree nodes with valuevalascur'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 == 1that means there is no depthdepth - 1at all, then create a tree node with valuevalas the new root of the whole original tree, and the original tree is the new root's left subtree.
Example 1:
- 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:
- Input: root = [4,2,null,3,1], val = 1, depth = 3
- Output: [4,2,null,1,1,3,null,null,1]
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. - The depth of the tree is in the range
[1, 104]. -100 <= Node.val <= 100-105 <= val <= 1051 <= depth <= the depth of tree + 1
Solution
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($val = 0, $left = null, $right = null) {
* $this->val = $val;
* $this->left = $left;
* $this->right = $right;
* }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @param Integer $val
* @param Integer $depth
* @return TreeNode
*/
function addOneRow($root, $val, $depth) {
return $this->dfs($root, $val, $depth, 1, false);
}
function dfs($root, $val, $depth, $curr, $isLeft) {
if ($root == null) {
if ($depth == 1) {
$root = new TreeNode($val);
}
return $root;
}
if ($depth == 1 && $root != null) {
$newNode = new TreeNode($val);
$newNode->left = $root;
$root = $newNode;
return $newNode;
}
if ($curr + 1 == $depth) {
$newNode = new TreeNode($val);
$newNode->left = $root->left;
$root->left = $newNode;
$newNode1 = new TreeNode($val);
$newNode1->right = $root->right;
$root->right = $newNode1;
return $root;
}
$this->dfs($root->left, $val, $depth, $curr + 1, true);
$this->dfs($root->right, $val, $depth, $curr + 1, false);
return $root;
}
}
Top comments (0)