题目主要信息

1、给一棵n个节点构成的二叉树

2、将每一层的节点向右循环位移k位

3、从最下一层开始位移，从下往上一次进行

方法一:层次遍历+循环移位

具体方法

由于是按照每一层的节点进行循环移位，因此我们可以首先进行树的层次遍历，得到每一层的结构。

按照题目要求，从最小面一层开始位移，为了确定移动之后的父节点，我们需要对每一行的所有节点的位置进行标记，通过index来进行保存，为了保证移动后位置的正确性，我们需要保留父节点的空子节点位置的index。

在获得index之后，我们可以通过对index值的计算，获得移动后的index，以及移动后的父节点，并且可以根据index奇偶值来判断为父节点的左子节点还是右子节点，具体如下图所示。

Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param k int整型 
     * @return TreeNode类
     */
    Map<TreeNode, Integer> map = new HashMap<>();
    public TreeNode cyclicShiftTree (TreeNode root, int k) {
        // write code here
        List<List<TreeNode>> list = levelOrder(root);
        for(int i=list.size()-1; i>0; i--){  //自底向上，依次移动
            List<TreeNode> child = list.get(i);
            List<TreeNode> parent = list.get(i-1);
            for(int j=0; j<child.size(); j++){
                TreeNode chi = child.get(j);
                TreeNode par = parent.get((map.get(chi)+k)%(parent.size()*2)/2);  //计算父节点
                if((map.get(chi)+k)%(parent.size()*2)%2==0){  //判断奇偶性，确定左右节点
                    par.left =  chi;
                }else{
                    par.right = chi;
                } 
            }
        }
        return root;
    }
    public List<List<TreeNode>> levelOrder(TreeNode root){
        List<List<TreeNode>> ans = new ArrayList<>();
        if(root==null){
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size()!=0){
            List<TreeNode> tmp = new ArrayList<>();
            int index = 0;
            for(int i=queue.size(); i>0; i--){
                TreeNode cur = queue.poll();
                index++;
                if(cur.val == -1){  //空节点不保存
                    continue;
                }
                tmp.add(cur);
                map.put(cur, index-1);
                queue.offer(cur.left==null?new TreeNode(-1):cur.left);  //空节点需要保留以计算index
                queue.offer(cur.right==null?new TreeNode(-1):cur.right);
                cur.left = null;
                cur.right = null;
            }
            ans.add(tmp);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(N)O(N)$，层次遍历的时间复杂度为$O(N)O(N)$，后续移动位置的时间复杂度也和节点个数相关
• 空间复杂度：$O(N)O(N)$，额外空间为层次遍历时使用的队列，和节点个数呈正相关

方法二：层次遍历+循环移位（C++版）

具体方法

上述的java版本，经过测试，只能通过8/10用例，第9个用例超时，但是时间复杂度上暂时没有想到优化的方式，于是想到使用C++重写，结构完全一致，但是C++版本可以跑通，不得不说，这个东西有时候就很玄学。

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类
     */
    map<TreeNode*, int> m;
    TreeNode* cyclicShiftTree(TreeNode* root, int k) {
        // write code here
        vector<vector<TreeNode*>> list = levelOrder(root);
        for(int i=list.size()-1; i>0; i--){  //自底向上，依次移动
            vector<TreeNode*> child = list.at(i);
            vector<TreeNode*> parent = list.at(i-1);
            for(int j=0; j<child.size(); j++){
                TreeNode* chi = child.at(j);
                TreeNode* par = parent.at((m[chi]+k)%(parent.size()*2)/2);  //计算父节点
                if((m[chi]+k)%(parent.size()*2)%2==0){  //判断奇偶性，确定左右节点
                    par->left = chi;
                }else{
                    par->right = chi;
                }
            }
        }
        return root;
    }
    vector<vector<TreeNode*>> levelOrder(TreeNode* root){
        vector<vector<TreeNode*>> ans;
        if(root==nullptr){
            return ans;
        }
        deque<TreeNode*> queue;
        queue.push_back(root);
        while(!queue.empty()){
            vector<TreeNode*> tmp;
            int index = 0;
            for(int i=queue.size(); i>0; i--){
                TreeNode* cur = queue.front();
                queue.pop_front();
                index++;
                if(cur->val==-1){  //空节点不保存
                    continue;
                }
                tmp.push_back(cur);
                m[cur] = index-1;
                queue.push_back(cur->left==nullptr ? new TreeNode(-1):cur->left);  //空节点需要保留以计算index
                queue.push_back(cur->right==nullptr ? new TreeNode(-1):cur->right);
                cur->left = nullptr;
                cur->right = nullptr;
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$O(N)O(N)$，同上
• 空间复杂度：$O(N)O(N)$，同上