623. Add One Row to Tree
题目描述
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.
|
|
|
|
Note:
The given d is in range [1, maximum depth of the given tree + 1].
The given binary tree has at least one tree node.
题目大意
给定一个二叉树的根,然后是value v
和depth d
,你需要在给定的深度d中添加一个值为v的节点行,根节点位于深度1。
给定一深度d
,二叉树root
,添加规则如下:
- 深度为d - 1的目标节点,创建两个值为
v
的节点,作为目标节点的左节点,记为vLeft,和右节点,记为vRight。 - 目标节点的左子树应该是vLeft的左子树,目标节点的原右子树应该是vRight的右子树。
- 如果
depth d
为1,则表示没有深度d - 1
,那么创建一个值为v
的节点作为root
的新根,而root
是新根的左子树。解题思路
递归,层序遍历。
如果d为1,则将v
作为根节点返回。
如果d为2,则将v
插入下一层。
代码
|
|