首页 > 试题广场 >

循环右移二叉树

[编程题]循环右移二叉树
  • 热度指数:2027 时间限制: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,点此查看相关信息

这道题你会答吗?花几分钟告诉大家答案吧!

问题信息

上传者:小小
难度:
0条回答 3141浏览

热门推荐

通过挑战的用户

查看代码