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

思路很简单，首先递归求出每个节点的深度，深度相同的节点是一起操作的，将他们存为一组。

移动要求从下到上，于是我们从最深的一层开始往上操作。修改第d层的节点排列，本质是要修改d-1层的节点的左右儿子。遍历d-1层，从左到右把每个左右孩子排成一列保存（空节点跳过），然后再遍历一遍，将d-1的每个点的左右儿子赋值为移动后的对应节点即可（注意是循环移动，超过的模总长度即可）。

#include <vector>
#include <algorithm>
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
	constexpr static int MAX = 1e5 + 3;

	std::vector<TreeNode*> deprec[MAX];//存储每个深度有哪些节点
	int maxdep = 0;

	void getdep(TreeNode* p, int dep) {//获取每个点深度和最大深度
		if (!p) return;
		deprec[dep].push_back(p);
		getdep(p->left, ++dep);
		getdep(p->right, dep);
		maxdep = std::max(maxdep, dep);
	}

	public:
		/**
		 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
		 *
		 * 
		 * @param root TreeNode类 
		 * @param k int整型 
		 * @return TreeNode类
		 */
		TreeNode* cyclicShiftTree(TreeNode* root, int k) {
			getdep(root, 0);
			for (int d = maxdep-1; ~d; --d) {//! 移动第d+1层，需要遍历第d层，root的dep为0，不用移动
				std::vector<TreeNode*> li;
				std::vector<TreeNode**> newli;
				for (auto p: deprec[d]) {
					if (p) {
						li.push_back(p->left);
						li.push_back(p->right);//li存下整个d层从左到右序列
						newli.push_back(&(p->left));
						newli.push_back(&(p->right));//newli存下从左到右序列的地址
					}				
				}

				for (int i = 0; i < li.size(); ++i) {
					*newli[(i+k)%li.size()] = li[i];//原地址赋新值
				}
			}
			return root;
		}
};