LeetCode题练习与总结：在二叉树中增加一行--623

一、题目描述

给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。

注意，根节点 root 位于深度 1 。

加法规则如下:

给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
cur 原来的左子树应该是新的左子树根的左子树。
cur 原来的右子树应该是新的右子树根的右子树。
如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。

示例 1:

输入: root = [4,2,6,3,1,5], val = 1, depth = 2
输出: [4,1,1,2,null,null,6,3,1,5]

示例 2:

输入: root = [4,2,null,3,1], val = 1, depth = 3
输出:  [4,2,null,1,1,3,null,null,1]

提示:

节点数在 [1, 10^4] 范围内
树的深度在 [1, 10^4]范围内
-100 <= Node.val <= 100
-10^5 <= val <= 10^5
1 <= depth <= the depth of tree + 1

二、解题思路

如果 depth 为 1，直接创建一个新的树节点作为根节点，原根节点作为新根节点的左子树。
使用递归方法遍历树，记录当前深度。当到达 depth - 1 时，对当前节点的左右子树进行操作。
在每个节点 cur 的左右子树上分别添加值为 val 的新节点，并将原左子树和右子树分别作为新节点的左子树和右子树。
递归结束条件：当遍历到叶子节点时，无需继续递归。

三、具体代码

class Solution {public TreeNode addOneRow(TreeNode root, int val, int depth) {// 如果depth为1，直接创建新根节点if (depth == 1) {TreeNode newRoot = new TreeNode(val);newRoot.left = root;return newRoot;}// 递归函数，用于在指定深度添加节点addNodes(root, val, depth, 1);return root;}private void addNodes(TreeNode node, int val, int depth, int currentDepth) {// 如果节点为空，直接返回if (node == null) {return;}// 如果当前深度为depth-1，则需要添加新节点if (currentDepth == depth - 1) {TreeNode leftTemp = node.left;TreeNode rightTemp = node.right;// 创建新节点并调整子树node.left = new TreeNode(val);node.right = new TreeNode(val);node.left.left = leftTemp;node.right.right = rightTemp;} else {// 继续递归遍历左右子树addNodes(node.left, val, depth, currentDepth + 1);addNodes(node.right, val, depth, currentDepth + 1);}}
}

这段代码首先处理了 depth 为 1 的情况，然后定义了一个递归函数 addNodes 来处理其他情况。在递归函数中，当到达 depth - 1 时，会在当前节点的左右子树上添加新节点，并将原来的子树连接到新节点的相应位置。

四、时间复杂度和空间复杂度

1. 时间复杂度

addOneRow 方法中，如果 depth 为 1，则直接创建新根节点，这个操作的时间复杂度是 O(1)。
addNodes 方法是一个递归函数，它会遍历树中的每个节点。对于每个节点，它会检查当前深度是否为 depth - 1。如果是，则在该节点下添加两个新节点，并将原来的子树连接到新节点上，这个操作的时间复杂度是 O(1)。
如果当前深度不是 depth - 1，则递归调用 addNodes 方法遍历左右子树。在递归过程中，每个节点都会被访问一次。
假设树有 n 个节点，则递归函数 addNodes 会被调用 n 次。因此，总的时间复杂度是 O(n)，其中 n 是树中节点的数量。

2. 空间复杂度

递归调用 addNodes 方法时，会在调用栈上占用空间。在最坏的情况下，如果树是完全不平衡的（例如，树退化成一条链），那么递归的深度将是 n，其中 n 是树中节点的数量。因此，递归调用栈的空间复杂度是 O(n)。
除了递归调用栈的空间，我们还需要考虑在 depth - 1 深度处添加新节点时使用的额外空间。在最坏的情况下，如果树是完全平衡的，那么在 depth - 1 深度处会有最多 2^(depth-1) 个节点。每个节点都需要两个新节点，因此需要 O(2^(depth-1)) 的额外空间。