如何将一个二叉树的节点逐层循环右移指定位数？

前言

本文将介绍一道某大厂的算法面试题，题目含义大意是如何将一个二叉树的节点逐层循环右移指定位数。

正文

题目描述：给出一个二叉树的头结点和一个正整数k，将这个二叉树每层的节点都水平右移k位，超出边界的话从左侧出现，从最后一层开始右移，右移完每一层之后，再向上，直到根节点，位移完毕。

如图所示，将下图中左侧二叉树右移2位后，转换结果为右侧二叉树的结构，每层都水平右移，超出边界则呈循环的形式从左侧再出现。

思路分析

抛开这个题目不谈，先思考下如何将一个数组中的元素右移k位？例如将数组[1,2,3,4,5,6,7,8]右移3位，结果为[6,7,8,1,2,3,4,5]。

数组右移

数组右移有一个技巧：左逆右逆整体逆。使用数组[1,2,3,4,5,6,7,8]解释一下，含义如下：

• 将数组分为两部分，左侧为1,2,3,4,5，右侧为6,7,8，右侧的位数为要移动的位数。
• 将左侧部分进行逆序，结果为：5,4,3,2,1。
• 将右侧部分进行逆序，结果为：8,7,6。
• 此时数组整体顺序为5,4,3,2,1,8,7,6。
• 再将数组整体进行逆序，结果为：6,7,8,1,2,3,4,5，此时就为数组整体右移3位的结果。

二叉树右移

二叉树右移和数组右移有一定的关系，比如可以把二叉树的每层节点都看成一个数组，当然要包含空节点。例如，上图所示二叉树每层用数组表示为：[[1],[2,3],[4,5,6,7],[null,8,9,null]]。

空节点使用null表示。

也就是把问题简化成了，将二叉树按层遍历转成几个数组，再将几个数组右移k位，然后再把数组还原为二叉树。

如果是数组中的元素个数，小于k呢？直接用k和元素个数取模运算即可。

在二叉树节点数组逆序的时候，要从下往上来，这样下面节点逆序好后，整合到父节点后，子节点就不用关注了。

在还原的时候，需要注意，遇到空节点需要跳过。

思路优化

上面思路分析可以完成目标，但是还是有更加优秀的方法，比如，不生成二维数组直接使用一维数组来放二叉树的节点，然后额外记录下每一层的起始位置。在右移时，可以通过计算节点间的对应关系而不是真正的右移，只是在还原的时候通过下标计算还原节点即可。

代码实现

定义二叉树节点：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

二叉树右移功能实现，这里采用第二种方式实现：

public class RightMoveInBinaryTree {
    public TreeNode[] queue = new TreeNode[300000];
    public int[] ends = new int[50];

    public TreeNode cyclicShiftTree(TreeNode root, int k) {
        int l = 0;
        int r = 0;
        queue[r++] = root;
        int level = 0;
        while (l != r) {
            ends[level] = r;
            while (l < ends[level]) {
                TreeNode cur = queue[l++];
                if (cur != null) {
                    queue[r++] = cur.left;
                    queue[r++] = cur.right;
                }
            }
            level++;
        }
        for (int i = level - 1; i > 0; i--) {
            int downLeft = ends[i - 1];
            int downRight = ends[i] - 1;
            int downRightSize = k % (downRight - downLeft + 1);
            int downIndex = downRightSize == 0 ? downLeft : (downRight - downRightSize + 1);
            int curLeft = i - 2 >= 0 ? ends[i - 2] : 0;
            int curRight = ends[i - 1] - 1;
            for (int j = curLeft; j <= curRight; j++) {
                if (queue[j] != null) {
                    queue[j].left = queue[downIndex];
                    downIndex = nextIndex(downIndex, downLeft, downRight);
                    queue[j].right = queue[downIndex];
                    downIndex = nextIndex(downIndex, downLeft, downRight);
                }
            }
        }
        return root;
    }
    public int nextIndex(int i, int l, int r) {
            return i == r ? l : i + 1;
    }

}

总结

本文将介绍如何将一个二叉树的节点逐层循环右移指定位数，文中介绍了两种方式来实现这个功能，第一种方式比较好理解一些，第二种方式相对复杂一些。