题意：
        现有一棵n个节点构成的二叉树，请你将每一层的节点向右循环位移k位。
        某层向右位移一位(即k=1)的含义为：
                1.若当前节点为左孩子节点，会变成当前节点的双亲节点的右孩子节点。
                2.若当前节点为右儿子，会变成当前节点的双亲节点的右边相邻兄弟节点的左孩子节点。(如果当前节点的双亲节点已经是最右边的节点了，则会变成双亲节点同级的最左边的节点的左孩子节点)
                3.该层的每一个节点同时进行一次位移。
                4.是从最下面的层开始位移，位移完每一层之后，再向上，直到根节点，位移完毕。

方法一：
bfs

思路：
        利用队列实现层次遍历来模拟右移操作。
        题意要求从最下层开始右移，但其实与从最上层开始右移效果一样。
        
        要一层一层的遍历，既要存储每一层的父节点，也要存储这一层父节点的所有儿子节点（儿子节点可以为 null ）;
        然后，循环右移所有的儿子节点，得到新的儿子节点序列，最后与新的父亲节点拼接即可。


class Solution {
public:
    
    TreeNode* cyclicShiftTree(TreeNode* root, int k) {
        if(root==nullptr)
            return root;
        queue<TreeNode*> q;//单向队列
        deque<TreeNode*> dq;//双向队列
        vector<TreeNode*> v;//存储父节点
        q.push(root);
        int num;//每一层可移动位置的个数
        while(!q.empty()){
            dq.clear();
            v.clear();
            int cnt=q.size();
            num=cnt*2;//每一层可移动位置的个数
            while(cnt--){//一层一层的遍历
                TreeNode *p=q.front();
                q.pop();
                v.push_back(p);//存储每一层的父节点
                dq.push_back(p->left);//存储每一层的左儿子节点（包含null节点）
                if(p->left)
                    q.push(p->left);
                dq.push_back(p->right);//存储每一层的右儿子节点（包含null节点）
                if(p->right)
                    q.push(p->right);
            }
            int step=k%num;//右移的步数取余
            for(int i=0;i<step;i++){//右移操作
                dq.push_front(dq.back());
                dq.pop_back();
            }
            for(int i=0;i<v.size();i++){//拼接新的儿子节点
                v[i]->left=dq.front();
                dq.pop_front();
                v[i]->right=dq.front();
                dq.pop_front();
            }
        }
        return root;
    }
    
};


时间复杂度：
空间复杂度：

方法二：
java模拟

思路：
        思路与方法一相同，直接模拟即可。



import java.util.*;



public class Solution {
    
    public TreeNode cyclicShiftTree (TreeNode root, int k) {
        if(root==null)
            return root;
        Queue<TreeNode> q=new LinkedList<>();//单向队列
        Deque<TreeNode> dq=new LinkedList<>();//双向队列
        Vector<TreeNode> v=new Vector<>();//存储父节点
        q.add(root);
        int num;//每一层可移动位置的个数
        while(!q.isEmpty()){
//             System.out.println(q.size());
            dq.clear();
            v.clear();
            int cnt=q.size();
            num=cnt*2;//每一层可移动位置的个数
            while((cnt--)!=0){//一层一层的遍历
                TreeNode p=q.poll();
                v.add(p);//存储每一层的父节点
                dq.addLast(p.left);//存储每一层的左儿子节点（包含null节点）
                if(p.left!=null)
                    q.add(p.left);
                dq.addLast(p.right);//存储每一层的右儿子节点（包含null节点）
                if(p.right!=null)
                    q.add(p.right);
            }
            int step=k%num;//右移的步数取余
            for(int i=0;i<step;i++){//右移操作
                dq.addFirst(dq.pollLast());
            }
            for(int i=0;i<v.size();i++){//拼接新的儿子节点
                v.get(i).left=dq.pollFirst();
                v.get(i).right=dq.pollFirst();
            }
        }
        return root;
    }
}

时间复杂度：
空间复杂度：