循环右移二叉树_

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

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

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

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

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

如果从最后一层开始对该二叉树的每一层循环位移 $k$ 位。以下方二叉树为例， $k=1$ ：

位移最后一层，5变成2的左孩子节点，4变成3的右孩子节点，如下图:

再位移倒数第二层，3变成1的左孩子节点，2变成1的右孩子的节点，它们的孩子节点随着一起位移，如下图：

根节点没有双亲节点，不用位移，位移完毕

现在给你这棵二叉树，请你返回循环右移 $k$ 位后的二叉树。

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ /** * NC146 循环右移二叉树 * @author d3y1 */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param root TreeNode类 * @param k int整型 * @return TreeNode类 */ public TreeNode cyclicShiftTree (TreeNode root, int k) { return solution(root, k); } /** * 层序遍历 * @param root * @param k * @return */ private TreeNode solution(TreeNode root, int k){ if(root == null){ return null; } Queue<QueueNode> queue = new LinkedList<>(); // level -> count HashMap<Integer,Integer> cntMap = new HashMap<>(); // level+seq -> treeNode HashMap<String,TreeNode> treeNodeMap = new HashMap<>(); // 树的层级从1开始 int level = 1; // 当前节点对应父层节点的索引位置从0开始 int index = 0; // 当前层级实际节点数目 int count = 1; // 当前层级实际节点序号(count-1) 从0开始 int seq = 0; queue.offer(new QueueNode(root, level, index, seq)); cntMap.put(level, count); int size,kIdx,upCnt,upSeq,upDirect; QueueNode queueNode; TreeNode treeNode,upTreeNode; while(!queue.isEmpty()){ size = queue.size(); level++; index = 0; count = 0; while(size-- > 0){ queueNode = queue.poll(); treeNode = queueNode.treeNode; // 加入队列 if(treeNode.left != null){ count++; queue.offer(new QueueNode(treeNode.left, level, index, count-1)); } index++; if(treeNode.right != null){ count++; queue.offer(new QueueNode(treeNode.right, level, index, count-1)); } index++; treeNode.left = null; treeNode.right = null; treeNodeMap.put(queueNode.level+"-"+queueNode.seq, treeNode); // 向右循环移动k位 if(queueNode.level > 1){ // 上层(父层) 实际节点数目 upCnt = cntMap.get(queueNode.level-1); // 向右循环移动k位到达的位置索引 kIdx = (queueNode.index+k)%(upCnt*2); // 对应的上层(父层) 节点序号 upSeq = kIdx/2; // 判断左右节点 upDirect = kIdx%2; // 根据父层层级+节点序号找到对应的应该挂载的父节点 upTreeNode = treeNodeMap.get((queueNode.level-1)+"-"+upSeq); // 进行挂载 if(upDirect == 0){ upTreeNode.left = treeNode; }else{ upTreeNode.right = treeNode; } } } cntMap.put(level, count); } return root; } private class QueueNode{ TreeNode treeNode; int level; int index; int seq; public QueueNode(TreeNode treeNode, int level, int index, int seq){ this.treeNode = treeNode; this.level = level; this.index = index; this.seq = seq; } } }

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)); } } }