题解 | #循环右移二叉树#

解题思路： 1.对二叉树进行填充，补全缺失的右子树或者左子树，补充的节点值为-1； 2.对二叉树进行层序遍历，获取每一层的节点。 3.对第二步获取到的节点进行遍历，分别获取父节点和子节点，对子节点进行往右偏移K位获取新的子节点，然后按序赋值给父节点，注意父节点的值如果为-1，是不可以赋值上去的。 4.对二叉树进行递归，去除掉值为-1的节点，得到的最终二叉树就是结果。

ArrayList<ArrayList<TreeNode>> res = new ArrayList<>();
public TreeNode cyclicShiftTree (TreeNode root, int k) {
    // write code here
    if(root==null){
        return null;
    }
    fillTreeNode(root);
    levelOfIterator(root,0);
    for (int i = res.size()-1; i > 0; i--) {
        ArrayList<TreeNode> parents = res.get(i-1);
        TreeNode parent;
        int num =0;
        ArrayList<TreeNode> childrens = res.get(i);
        handleChildren(childrens,k);
        for (TreeNode treeNode : parents) {
            parent = treeNode;
            if (parent.val != -1) {
                parent.left = childrens.get(num);
                num++;
                parent.right = childrens.get(num);
                num++;
            }
        }
    }
    modifyTreeNode(root);
    return root;
}
//去除值为-1的节点
private void modifyTreeNode(TreeNode root) {
    if(root==null){
        return;
    }
    if(root.left!=null&&root.left.val==-1){
        root.left=null;
    }
    if(root.right!=null&&root.right.val==-1){
        root.right=null;
    }
    modifyTreeNode(root.left);
    modifyTreeNode(root.right);
}
//把子节点向右偏移K个位置
private void handleChildren(ArrayList<TreeNode> children, int k) {
    k=k% children.size();
    TreeNode last ;
    while (k>0){
        last = children.get(children.size()-1);
        for (int i = children.size()-1; i > 0; i--) {
            children.set(i, children.get(i-1));
        }
        children.set(0,last);
        k--;
    }
}
//层序遍历
private void levelOfIterator(TreeNode root,int level) {
    if(level==res.size()){
        res.add(new ArrayList<>());
    }
    ArrayList<TreeNode> treeNodeArrayList = res.get(level);
    treeNodeArrayList.add(root);
    if(root.left!=null){
        levelOfIterator(root.left,level+1);
    }
    if(root.right!=null){
        levelOfIterator(root.right,level+1);
    }
}
//填充二叉树
private void fillTreeNode(TreeNode root) {
    if(root==null||root.val==-1){
        return;
    }
    if(root.left == null){
        root.left=new TreeNode(-1);
    }
    if(root.right == null){
        root.right=new TreeNode(-1);
    }
    fillTreeNode(root.left);
    fillTreeNode(root.right);
}