二叉树题目:在二叉树中增加一行

这篇具有很好参考价值的文章主要介绍了二叉树题目:在二叉树中增加一行。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

标题和出处

标题:在二叉树中增加一行

出处:623. 在二叉树中增加一行

难度

5 级

题目描述

要求

给定一个二叉树的根结点 root \texttt{root} root 和两个整数 val \texttt{val} val depth \texttt{depth} depth,在给定的深度 depth \texttt{depth} depth 处添加一行值为 val \texttt{val} val 的结点。

注意,根结点 root \texttt{root} root 位于深度 1 \texttt{1} 1

添加规则如下:

  • 给定整数 depth \texttt{depth} depth,对于深度为 depth   -   1 \texttt{depth - 1} depth - 1 的每个非空树结点 cur \texttt{cur} cur,创建两个值为 val \texttt{val} val 的树结点作为 cur \texttt{cur} cur 的左子树根和右子树根。
  • cur \texttt{cur} cur 原来的左子树应该是新的左子树根的左子树。
  • cur \texttt{cur} cur 原来的右子树应该是新的右子树根的右子树。
  • 如果 depth   =   1 \texttt{depth = 1} depth = 1 意味着不存在深度 depth   -   1 \texttt{depth - 1} depth - 1,则创建一个值为 val \texttt{val} val 的树结点作为新的根结点,原始树作为新的根结点的左子树。

示例

示例 1:

二叉树题目:在二叉树中增加一行,数据结构和算法,# 树,树,二叉树

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

示例 2:

二叉树题目:在二叉树中增加一行,数据结构和算法,# 树,树,二叉树

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

数据范围

  • 树中结点数目在范围 [1,   10 4 ] \texttt{[1, 10}^\texttt{4}\texttt{]} [1, 104]
  • 树的深度在范围 [1,   10 4 ] \texttt{[1, 10}^\texttt{4}\texttt{]} [1, 104]
  • -100 ≤ Node.val ≤ 100 \texttt{-100} \le \texttt{Node.val} \le \texttt{100} -100Node.val100
  • -10 5 ≤ val ≤ 10 5 \texttt{-10}^\texttt{5} \le \texttt{val} \le \texttt{10}^\texttt{5} -105val105
  • depth \texttt{depth} depth 的最小可能值为 1 \texttt{1} 1,最大可能值为树的深度加 1 \texttt{1} 1

解法一

思路和算法

如果 depth = 1 \textit{depth} = 1 depth=1,则创建值为 val \textit{val} val 的新的根结点,将原二叉树作为新的根结点的左子树,返回新的根结点即可。

depth > 1 \textit{depth} > 1 depth>1 时,添加一行结点不会改变根结点,只要定位到添加结点的层,完成添加操作之后返回根结点即可。

根据添加规则,结点应该添加在深度 depth \textit{depth} depth 的行。令 level = depth − 1 \textit{level} = \textit{depth} - 1 level=depth1,需要定位到第 level \textit{level} level 层的全部结点,对于该层的每个结点添加两个子结点,并将原左子树和原右子树分别作为新左子结点的左子树和新右子结点的右子树。

定位到特定层添加结点可以使用深度优先搜索实现,深度优先搜索的过程中需要记录位于当前结点时应该添加在当前子树的哪一层,初始时位于根结点,层数 level = depth − 1 \textit{level} = \textit{depth} - 1 level=depth1。搜索过程中,如果 level = 1 \textit{level} = 1 level=1,则对于当前结点添加两个子结点,并将原左子树和原右子树分别作为新左子结点的左子树和新右子结点的右子树。如果 level > 1 \textit{level} > 1 level>1,则对于每个非空结点,将层数减 1 1 1 之后继续深度优先搜索。

上述过程是一个递归的过程,递归的终止条件是 level = 1 \textit{level} = 1 level=1,当 level > 1 \textit{level} > 1 level>1 时调用递归。

代码

class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            return new TreeNode(val, root, null);
        }
        insert(root, val, depth - 1);
        return root;
    }

    public void insert(TreeNode node, int val, int level) {
        TreeNode left = node.left, right = node.right;
        if (level == 1) {
            node.left = new TreeNode(val, left, null);
            node.right = new TreeNode(val, null, right);
        } else {
            if (left != null) {
                insert(left, val, level - 1);
            }
            if (right != null) {
                insert(right, val, level - 1);
            }
        }
    }
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。每个结点最多访问一次。

  • 空间复杂度: O ( depth ) O(\textit{depth}) O(depth)。空间复杂度主要是递归调用的栈空间,栈空间的深度是 O ( depth ) O(\textit{depth}) O(depth)

解法二

思路和算法

也可以使用广度优先搜索实现,具体做法是使用层序遍历定位到添加结点的层,然后对于该层的每个结点添加两个子结点,并将原左子树和原右子树分别作为新左子结点的左子树和新右子结点的右子树。

从根结点开始依次遍历每一层的结点,在层序遍历的过程中需要记录遍历的层数,并区分不同结点所在的层,确保每一轮访问的结点为同一层的全部结点。遍历每一层结点之前首先得到当前层的结点数,即可确保每一轮访问的结点为同一层的全部结点。遍历完一层结点之后需要将层数加 1 1 1

使用队列存储待访问的结点,初始时队列中只有根结点,层数为 1 1 1。当层数等于 depth − 1 \textit{depth} - 1 depth1 时,队列中的结点即为需要添加子结点的全部结点,对于队列中的每个结点添加两个子结点,并将原左子树和原右子树分别作为新左子结点的左子树和新右子结点的右子树。

代码

class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            return new TreeNode(val, root, null);
        }
        int level = 1;
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty() && level < depth - 1) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            level++;
        }
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode left = node.left, right = node.right;
            node.left = new TreeNode(val, left, null);
            node.right = new TreeNode(val, null, right);
        }
        return root;
    }
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。每个结点最多被访问一次。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度主要是队列空间,队列内元素个数不超过 n n n文章来源地址https://www.toymoban.com/news/detail-739691.html

到了这里,关于二叉树题目:在二叉树中增加一行的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【刷题笔记8.11】LeetCode题目:二叉树中序遍历、前序遍历、后序遍历

    (一)题目描述 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 (二)分析 二叉树中序遍历,遍历顺序:左节点 -》 根节点 -》 右节点 ( 注意:二叉树的前、中、后序遍历就是以根为基准,前序遍历根在最前面,中序遍历根在中间,后序遍历根在最后面 ) (三)

    2024年02月13日
    浏览(39)
  • 【数据结构】二叉树中的递归问题(超详细画图~)

    和光同尘_我的个人主页 不管风吹浪打,胜似闲庭信步。 --毛泽东 我本来还说上节难来着,没想到这节更难🥲 不过我既然会了保证xdm也能看懂👍 首先回顾下二叉树的概念 二叉树是由:空树 或者非空树(根节点,根节点的左子树、根节点的右子树)组成的 从概念中可以看出

    2024年02月07日
    浏览(38)
  • 2023-05-10:给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉树中,存在一条一直向下的路径 且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值,

    2023-05-10:给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉树中,存在一条一直向下的路径 且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值,那么请你返回 True 否则返回 False 。 一直向下的路径的意思是:从树中某个节点开始,一直连

    2024年02月03日
    浏览(47)
  • 【数据结构】二叉树经典题目

    相信大部分人看了题目描述之后,都会和我一样一脸的懵逼。直到我看到了一个描述才恍然大悟 分为3种情况: 左右都为空 --省略 右为空,左不为空 – 省略 左为空,右不为空–不省略 这里复习一下二叉树的前序遍历、中序遍历、和后序遍历 前序的结果是:ABDEGCF 中序的结

    2024年02月10日
    浏览(54)
  • 【数据结构】二叉树常见题目

    此乃本人自用版本,用于复习回顾! 所以部分题目不会有过大详细的解析,不懂的可以评论!笔者将竭力为你解答 满⼆叉树:如果⼀棵⼆叉树只有度为0的结点和度为2的结点,并且度为0的结点在同⼀层上,则这棵⼆叉树为满⼆叉树 高度为h的满二叉树,共有 2^h -1 个节点 完全

    2024年02月13日
    浏览(38)
  • 【数据结构】二叉树的相关操作以及OJ题目

    当一个树不是满二叉树或完全二叉树时,它是不适合使用数组存储的,它应该使用链式结构来存储。 再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是: 空树 非空:根节点,根节点的左子树、根节点的右子树组成的。 从概念中可以看出,二叉树定义是递归式的,因

    2024年03月19日
    浏览(50)
  • 979. 在二叉树中分配硬币(力扣)

    给你一个有 n 个结点的二叉树的根结点 root ,其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。 在一次移动中,我们可以选择两个相邻的结点,然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到子结点,或者从子结点移动到

    2024年02月16日
    浏览(32)
  • 【算法】Distribute Coins in Binary Tree 在二叉树中分配硬币

    给定一个有 N 个结点的二叉树的根结点 root,树中的每个结点上都对应有 node.val 枚硬币,并且总共有 N 枚硬币。 在一次移动中,我们可以选择两个相邻的结点,然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点,或者从子结点移动到父结点。

    2024年02月16日
    浏览(40)
  • C++力扣题目700--二叉搜索树中的搜索

    给定二叉搜索树(BST)的根节点  root  和一个整数值  val 。 你需要在 BST 中找到节点值等于  val  的节点。 返回以该节点为根的子树。 如果节点不存在,则返回  null  。 示例 1: 示例 2:   之前我们讲的都是普通二叉树,那么接下来看看二叉搜索树。 在关于二叉树,你该了

    2024年01月17日
    浏览(53)
  • 算法---二叉树中的最大路径和

    二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ,返回其 最大路径和 。 示

    2024年02月11日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包