循环右移二叉树

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类
     */
    public TreeNode cyclicShiftTree (TreeNode root, int k) {
        // 存储第一层节点
        Queue<TreeNode> queue1 = new LinkedList<>();
        // 存储第一层节点的子节点
        Queue<TreeNode> queue2 = new LinkedList<>();
    
        queue1.offer(root);
        addNode(queue2, root);

        while (!queue1.isEmpty()) {
            int size = queue1.size();

            moveK(queue1, k);
            moveK(queue2, k);

            while (size > 0) {
                changeNode(queue1, queue2);
                size--;
            }
        }
        return root;
    }

    public static void changeNode(Queue<TreeNode> queue1, Queue<TreeNode> queue2) {
        // 取出根节点 tmp
        TreeNode tmp = queue1.poll();

        // 为根节点添加子节点，当子节点val为0时，子节点为空
        TreeNode childLeft = queue2.poll();
        if (childLeft.val == 0) {
            tmp.left = null;
        }else {
            queue1.offer(childLeft);
            tmp.left = childLeft;
            addNode(queue2, childLeft);
        }

        TreeNode childRight = queue2.poll();
        if (childRight.val == 0) {
            tmp.right = null;
        }else {
            queue1.offer(childRight);
            tmp.right = childRight;
            addNode(queue2, childRight);
        }
}

    // 右移 k 位
    public static void moveK(Queue<TreeNode> queue, int k) {
        while (k > 0) {
            queue.offer(queue.poll());
            k--;
        }
    }

    // 添加节点
    public static void addNode(Queue<TreeNode> queue, TreeNode root) {
        if (root.val == 0) {
            return;
        }
        //  为了使得叶子节点，在右移的过程中获得子节点，将null转换为 val=0 的子节点，之后再识别出来，转化为null
        if (root.left != null) {
            queue.offer(root.left);
        }else {
            queue.offer(new TreeNode(0));
        }

        if (root.right != null) {
            queue.offer(root.right);
        }else {
            queue.offer(new TreeNode(0));
        }
  
    }

}