当前位置:   article > 正文

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

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

一【题目类别】

  • 广度优先遍历

二【题目难度】

  • 中等

三【题目编号】

  • 623.在二叉树中增加一行

四【题目描述】

  • 给定一个二叉树的根 root 和两个整数 valdepth ,在给定的深度 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 , 1 0 4 ] 范围内 节点数在 [1, 10^4] 范围内 节点数在[1,104]范围内
  • 树的深度在 [ 1 , 1 0 4 ] 范围内 树的深度在 [1, 10^4]范围内 树的深度在[1,104]范围内
  • − 100 < = N o d e . v a l < = 100 -100 <= Node.val <= 100 100<=Node.val<=100
  • − 1 0 5 < = v a l < = 1 0 5 -10^5 <= val <= 10^5 105<=val<=105
  • 1 < = d e p t h < = t h e   d e p t h   o f   t r e e   + 1 1 <= depth <= the\ depth\ of\ tree\ + 1 1<=depth<=the depth of tree +1

七【解题思路】

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

八【时间频度】

  • 时间复杂度: O ( n ) O(n) O(n) n n n为传入的二叉树的节点个数
  • 空间复杂度: O ( n ) O(n) O(n) n 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;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  1. 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:
            return
        if 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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  1. 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
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90

十【提交结果】

  1. Java语言版
    在这里插入图片描述

  2. Python语言
    在这里插入图片描述

  3. C语言版
    在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/1001764
推荐阅读
相关标签
  

闽ICP备14008679号