LeetCode 补充题 185. 逐层循环右移二叉树

约 6 分钟
文章信息 2 个分类 2 个标签
分类
补充题 困难
标签
树 广度优先搜索

题目描述

牛客原题： ✅ 补充题 185. 逐层循环右移二叉树

将二叉树各层的孩子槽位向右循环移动 k 位，空槽位也参与。一层的槽位依次是该层每个父节点的左、右孩子。

操作从最底层向上进行，移动节点时带着它当前的整棵子树。根节点不移动。

示例 1：

输入： root = [1,2,3,4], k = 2
输出： [1,2,3,null,null,4]
解释： 用层序序列表示树，null 表示空槽。底层槽位 [4,null,null,null] 右移两位后为 [null,null,4,null]，所以 4 成为 3 的左孩子。根的两个孩子不变。

提示：

  • k 为非负整数。
  • 空孩子槽位也参与循环移动。
  • 按层从下往上处理，节点携带当前子树移动，根节点位置不变。

题意分析

移动对象是孩子指针槽位，空槽也占一个位置，不能只对非空节点值旋转。节点移动时携带整棵子树，所以需要先确定原始各层节点，再按题目要求从底向上调整。

解法：保留空槽并从底层向上旋转

核心思路

[!blue]

先层序保存各层的非空节点引用，固定每一轮的父节点列表。对包含 m 个父节点的一层，将它们的左、右孩子依次复制到长度为 2m 的槽位数组，空指针也照常写入。

右移量先取 shift = k % (2m)，旧槽位 i 写到 (i+shift) % (2m)。目标下标除以 2 得父节点编号，奇偶决定左或右孩子。先复制全部旧槽再回写，避免前面的改写覆盖后面尚未读取的指针。

从最深父节点层开始，子树内部先完成调整，再随上层节点整体移动；原始父节点列表不会被新的层次关系干扰。根位置不变，空树直接返回，单节点树没有可处理的孩子层。

解题步骤

  1. 层序收集每层原有非空节点。
  2. 从最深的父节点层向上，按父节点顺序复制全部左右孩子槽位，保留 null。
  3. 把每个旧槽位映射到右移后的新槽位，回写对应父节点的左或右指针。

代码实现

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode rotateLevels(TreeNode root, int k) {
        if (root == null) {
            return null;
        }

        List<List<TreeNode>> levels = new ArrayList<>();
        List<TreeNode> level = new ArrayList<>();

        level.add(root);

        while (!level.isEmpty()) {
            levels.add(level);
            List<TreeNode> next = new ArrayList<>();

            for (TreeNode node : level) {
                if (node.left != null) {
                    next.add(node.left);
                }

                if (node.right != null) {
                    next.add(node.right);
                }
            }

            level = next;
        }

        for (int depth = levels.size() - 2; depth >= 0; depth--) {
            List<TreeNode> parents = levels.get(depth);
            int width = parents.size() * 2;
            TreeNode[] slots = new TreeNode[width];

            for (int i = 0; i < parents.size(); i++) {
                slots[2 * i] = parents.get(i).left;
                slots[2 * i + 1] = parents.get(i).right;
            }

            int shift = k % width;

            for (int i = 0; i < width; i++) {
                int dest = (i + shift) % width;
                TreeNode parent = parents.get(dest / 2);

                if ((dest & 1) == 0) {
                    parent.left = slots[i];
                } else {
                    parent.right = slots[i];
                }
            }
        }

        return root;
    }
}

type TreeNode struct {
    Val         int
    Left, Right *TreeNode
}

func rotateLevels(root *TreeNode, k int) *TreeNode {
    if root == nil {
        return nil
    }
    levels := [][]*TreeNode{}
    level := []*TreeNode{
        root,
    }
    for len(level) > 0 {
        levels = append(levels, level)
        next := []*TreeNode{}
        for _, node := range level {
            if node.Left != nil {
                next = append(next, node.Left)
            }
            if node.Right != nil {
                next = append(next, node.Right)
            }
        }
        level = next
    }
    for depth := len(levels) - 2; depth >= 0; depth-- {
        parents := levels[depth]
        width := len(parents) * 2
        slots := make([]*TreeNode, width)
        for i, node := range parents {
            slots[2*i], slots[2*i+1] = node.Left, node.Right
        }
        shift := k % width
        for i, node := range slots {
            dest := (i + shift) % width
            parent := parents[dest/2]
            if dest%2 == 0 {
                parent.Left = node
            } else {
                parent.Right = node
            }
        }
    }
    return root
}

复杂度分析

  • 时间复杂度：$O(n)$。
  • 空间复杂度：额外空间 $O(n)$。

关键点总结

[!green]

先复制后回写避免覆盖尚未搬移的指针；从底层处理使节点携带已调整的子树移动，上一层父节点集合仍是原始集合。

易错点总结

[!yellow]

k为非负整数；空孩子槽位也移动；必须自底向上，不能只旋转每层节点值。

相似题目

题目 难度 关联与区别
102. 二叉树的层序遍历 中等 先通过层序遍历保存各层原节点，本题随后重连孩子指针而非只输出节点值。
189. 轮转数组 中等 同样把位置 i 映射到 (i+k)%长度，本题旋转的是含空值的孩子槽位。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/05041241
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！