【LeetCode每日一题】——623.在二叉树中增加一行

一【题目类别】

• 广度优先遍历

二【题目难度】

• 中等

三【题目编号】

• 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<=thedepthoftree+1$

七【解题思路】

• 这道题还是比较简单的，就是对于二叉树的层数遍历的一种变种
• 我们只需要找到待插入行的上一行，然后将目标行插入即可
• 寻找待插入行的上一行的这个过程，可以使用广度优先搜索
• 具体细节可以查看下面的代码

八【时间频度】

• 时间复杂度：$O(n)$，$n$为传入的二叉树的节点个数
• 空间复杂度：$O(n)$，$n$为传入的二叉树的节点个数

九【代码实现】

1. Java语言版

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode addOneRow(TreeNode root, int val, int depth) {// 边界条件if (depth == 1) {return new TreeNode(val, root, null);}// 保存当前层节点List<TreeNode> curLevel = new ArrayList<TreeNode>();curLevel.add(root);// 使用广度优先搜索要插入行的上一行for (int i = 1; i < depth - 1; i++) {List<TreeNode> temp = new ArrayList<TreeNode>();for (TreeNode node : curLevel) {if (node.left != null) {temp.add(node.left);}if (node.right != null) {temp.add(node.right);}}curLevel = temp;}// 插入目标行for (TreeNode node : curLevel) {node.left = new TreeNode(val, node.left, null);node.right = new TreeNode(val, null, node.right);}// 返回结果return root;}
}

2. Python语言版

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:# 边界条件if root == None:returnif depth == 1:return TreeNode(val, root, None)# 保存当前层节点cur_level = [root]# 使用广度优先搜索要插入行的上一行for _ in range(1, depth - 1):temp = []for node in cur_level:if node.left:temp.append(node.left)if node.right:temp.append(node.right)cur_level = temp# 插入目标行for node in cur_level:node.left = TreeNode(val, node.left, None)node.right = TreeNode(val, None, node.right)# 返回结果return root

3. C语言版

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
struct TreeNode* addOneRow(struct TreeNode* root, int val, int depth)
{// 边界条件if (root == NULL){struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));node->val = val;node->left = NULL;node->right = NULL;return node;}if (depth == 1){struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));node->val = val;node->left = root;node->right = NULL;return node;}// 初始化队列struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 10001);int front = 0;int rear = 0;queue[rear++] = root;// 存储树高int level = 1;// 使用广度优先搜索算法插入目标节点while (front != rear){// 当前层节点数量int size = rear - front;// 如果找到目标行，直接插入目标节点即可if (level == depth - 1){for (int i = 0; i < size; i++){struct TreeNode* node = queue[front++];struct TreeNode* nodeLeft = (struct TreeNode*)malloc(sizeof(struct TreeNode));nodeLeft->val = val;nodeLeft->left = node->left;nodeLeft->right = NULL;node->left = nodeLeft;struct TreeNode* nodeRight = (struct TreeNode*)malloc(sizeof(struct TreeNode));nodeRight->val = val;nodeRight->left = NULL;nodeRight->right = node->right;node->right = nodeRight;}break;}// 处理当前层的节点，并将下一层的节点加入队列for (int i = 0; i < size; i++){struct TreeNode* node = queue[front++];if (node->left != NULL){queue[rear++] = node->left;}if (node->right != NULL){queue[rear++] = node->right;}}// 获取二叉树的层数level++;}// 释放内存free(queue);// 返回结果return root;}

十【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C语言版