题目描述

现有一棵n个节点构成的二叉树，请你将每一层的节点向右循环位移k位。某层向右位移一位(即k=1)的含义为：

1.若当前节点为左孩子节点，会变成当前节点的双亲节点的右孩子节点。

2.若当前节点为右儿子，会变成当前节点的双亲节点的右边相邻兄弟节点的左孩子节点。(如果当前节点的双亲节点已经是最右边的节点了，则会变成双亲节点同级的最左边的节点的左孩子节点)

3.该层的每一个节点同时进行一次位移。

4.是从最下面的层开始位移，位移完每一层之后，再向上，直到根节点，位移完毕。

解题思路：分层递归+右移取模

假设我们知道树的某一层的全部节点，构成一个数组v1（v1不能包含空节点）。那么我们很容易得到下一层的全部节点构成的数组v2。易知v2的长度是v1的二倍。

令v2数组的长度为n。我们对v2的每个节点v2[i]右移k次，其最终位置在(i + k) % n处。这样就得到一个新的v2数组。

此时再根据v1与v2的对应关系，重新设置v1中每个节点的左右孩子节点，右移完成！

接下来将v2数组中的空节点全部移除，然后就能得到其更下一层的全部节点构成的数组v3。重复上述步骤，完成每一层的节点右移。

下面给出c++代码。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param k int整型 
     * @return TreeNode类
     */
    TreeNode* cyclicShiftTree(TreeNode* root, int k) {
        vector<TreeNode*> next(1, root);
        fun(next, k);
        return root;
    }

    void fun(vector<TreeNode*> &v, int k) {
        if(v.size() == 0) return;
        int n = v.size() + v.size();
        int pos = k % n; //下标0的元素右移k次后的位置
        vector<TreeNode*> son(n + pos); //将数组容量增加pos
        for(auto & node : v) {
            son[pos++] = node->left;
            son[pos++] = node->right;
        }
        for(int i = son.size() - 1; i >= n; --i) {
            son[i - n] = son[i]; //将超出n范围的元素放回[0, n-1]区间内
        }
        for(int i = 0; i < v.size(); ++i) { //重新设置v数组中每个节点的左右孩子（右移k次后）
            int i2 = i + i;
            v[i]->left = son[i2];
            v[i]->right = son[i2 + 1];
        }
        vector<TreeNode*> next;
        for(int i = 0; i < n; ++i) {
            if(son[i]) next.push_back(son[i]); //去掉其中的空节点
        }
        fun(next, k); //递归下一层
    }
};