623. Add One Row to Tree

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 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:

• 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 <= 105
• 1 <= 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; }
}