首页 > 试题广场 >

循环右移二叉树

[编程题]循环右移二叉树
  • 热度指数:2610 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
现有一棵个节点构成的二叉树,请你将每一层的节点向右循环位移位。某层向右位移一位(即)的含义为:
1.若当前节点为左孩子节点,会变成当前节点的双亲节点的右孩子节点。
2.若当前节点为右儿子,会变成当前节点的双亲节点的右边相邻兄弟节点的左孩子节点。(如果当前节点的双亲节点已经是最右边的节点了,则会变成双亲节点同级的最左边的节点的左孩子节点)
3.该层的每一个节点同时进行一次位移。
4.是从最下面的层开始位移,位移完每一层之后,再向上,直到根节点,位移完毕。

如果从最后一层开始对该二叉树的每一层循环位移位。以下方二叉树为例,

      1
     / \
    2   3
       / \
      4   5
位移最后一层,5变成2的左孩子节点,4变成3的右孩子节点,如下图:
      1
     / \
    2   3
   /     \
  5       4
再位移倒数第二层,3变成1的左孩子节点,2变成1的右孩子的节点,它们的孩子节点随着一起位移,如下图:
      1
     / \
    3   2
    \   /
     4 5
根节点没有双亲节点,不用位移,位移完毕

现在给你这棵二叉树,请你返回循环右移位后的二叉树。
示例1

输入

{1,2,3,#,#,4,5},1

输出

{1,3,2,#,4,5}

说明

解释见题面描述。     
示例2

输入

{1,2,3,4},2

输出

{1,2,3,#,#,4}

说明

      1
     / \
    2   3
   /
  4
变为
      1
     / \
    2   3
       /
      4
示例3

输入

{1,#,3,4,5},1

输出

{1,3,#,5,4}

说明

    1
     \
      3
     / \
    4   5
变为
    1
     \
      3
     / \
    5   4
变为
        1
       /
      3
     / \
    5   4

备注:
树的节点个数在之间,且保证该树上每个节点的编号不同,节点编号并非按顺序排列,

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
头像 代码界的小白
发表于 2022-01-02 23:49:15
题目主要信息 1、给一棵n个节点构成的二叉树 2、将每一层的节点向右循环位移k位 3、从最下一层开始位移,从下往上一次进行 方法一:层次遍历+循环移位 具体方法 由于是按照每一层的节点进行循环移位,因此我们可以首先进行树的层次遍历,得到每一层的结构。 按照题目要求,从最小面一层开始位移,为了确定移动 展开全文
头像 godhands
发表于 2022-01-03 16:43:39
描述 题目描述 首先是给了我们一颗二叉树,然后给了我们一个kkk的值,然后让我们去把整棵树的每一层都向右移动kkk个 如果大家对二叉树不理解,可以先看一下牛客的这一道题目和这道题目我的题解 修建叶子-(传送门) 样例解释 {1,#,3,4,5},1 这里我们拿好看的图解来解释一下这个问题 然 展开全文
头像 认认真真coding
发表于 2022-01-27 21:17:48
循环右移二叉树 题目描述 现有一棵n个节点构成的二叉树,请你将每一层的节点向右循环位移k位。某层向右位移一位(即k=1)的含义为: 1.若当前节点为左孩子节点,会变成当前节点的双亲节点的右孩子节点。 2.若当前节点为右儿子,会变成当前节点的双亲节点的右边相邻兄弟节点的左孩子节点。(如果当前节点的双亲 展开全文
头像 君鸿
发表于 2025-01-09 17:39:14
题目描述现有一棵n个节点构成的二叉树,请你将每一层的节点向右循环位移k位。某层向右位移一位(即k=1)的含义为:1.若当前节点为左孩子节点,会变成当前节点的双亲节点的右孩子节点。2.若当前节点为右儿子,会变成当前节点的双亲节点的右边相邻兄弟节点的左孩子节点。(如果当前节点的双亲节点已经是最右边的节点 展开全文
头像 George_Plover
发表于 2022-01-05 23:09:40
题解 题意整理: 基本题意 ​ 给出一棵 nnn 个节点的二叉树,现在定义了二叉树的一次右平移操作,问二叉树右平移 kkk 次后长什么样。 数据范围 ​ 1≤n≤105,1≤k≤1001\le n \le 10^5, 1\le k \le 1001≤n≤105,1≤k≤100 。 右平移操作 展开全文
头像 小步惊惊
发表于 2022-07-04 15:36:35
解题思路:1.对二叉树进行填充,补全缺失的右子树或者左子树,补充的节点值为-1; 2.对二叉树进行层序遍历,获取每一层的节点。 3.对第二步获取到的节点进行遍历,分别获取父节点和子节点,对子节点进行往右偏移K位获取新的子节点,然后按序赋值给父节点,注意父节点的值如果为-1 展开全文
头像 AimerAimer
发表于 2022-03-10 17:06:49
题意:         现有一棵n个节点构成的二叉树,请你将每一层的节点向右循环位移k位。         某层向右位移一位(即k=1)的 展开全文
头像 小步惊惊
发表于 2022-07-03 15:35:26
解题思路:1.对二叉树进行填充,补全缺失的右子树或者左子树,补充的节点值为-1; 2.对二叉树进行层序遍历,获取每一层的节点。 3.对第二步获取到的节点进行遍历,分别获取父节点和子节点,对子节点进行往右便宜K位获取新的子节点,然后按序赋值给父节点,注意父节点的值如果为 展开全文
头像 译言丁真
发表于 2022-02-10 17:42:26
思路很简单,首先递归求出每个节点的深度,深度相同的节点是一起操作的,将他们存为一组。 移动要求从下到上,于是我们从最深的一层开始往上操作。修改第d层的节点排列,本质是要修改d-1层的节点的左右儿子。遍历d-1层,从左到右把每个左右孩子排成一列保存(空节点跳过),然后再遍历一遍,将d-1的每个点的左右 展开全文
头像 ezis
发表于 2024-03-16 21:24:00
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) { 展开全文

问题信息

上传者:小小
难度:
14条回答 5252浏览

热门推荐

通过挑战的用户

查看代码
循环右移二叉树