0623. Add One Row to Tree

题目信息

题号:

0623

难度:

Medium

主题:

二叉树、指定深度、插入新节点、旧子树重接

原题:

LeetCode 0623

重点:

在给定深度插入整行节点、旧左子树接到新左节点左侧、旧右子树接到新右节点右侧、depth=1 时创建新根

题目重述

给定非空二叉树根节点 root、整数 val 和一基深度 depth,在树的第 depth 层插入一行值均为 val 的节点,并返回修改后的根节点。

当 depth > 1 时,对原第 depth-1 层的每个节点 cur 创建新的左、右孩子:cur 原来的左子树成为新左孩子的左子树,原来的右子树成为新右孩子的右子树,其余两个连接为空。当 depth = 1 时,新建值为 val 的根节点,并把原树作为其左子树。节点数位于 [1, 10^4],depth 保证位于 [1, 原树最大深度 + 1]。

自建示例

在内部层插入新行:

输入:root = [4,2,6,1,3,5,7],val = 9,depth = 3
输出:根 4 的下一层仍为 2、6;它们各自新增两个值为 9 的孩子
解释:原节点 1、3、5、7 分别接到对应新节点的左、右外侧,原有四棵子树不会丢失。

在根节点上方插入:

输入:root = [8,3,10],val = 0,depth = 1
输出:[0,8,null,3,10]
解释:新节点 0 成为根,原树整体成为它的左子树,新根没有右孩子。