C 解法, 执行用时: 40ms, 内存消耗: 9472KB, 提交时间: 2022-01-22
void st(struct TreeNode** t1,struct TreeNode** t2,int s1,int s2,int k);
struct TreeNode* cyclicShiftTree(struct TreeNode* root, int k ) {
struct TreeNode** t1;
struct TreeNode** t2;
int s2=0;
int s=0;
t1=(struct TreeNode**)malloc(sizeof(struct TreeNode*));
t1[0]=root;
if(t1[0]->left!=0)
++s2;
if(t1[0]->right!=0)
++s2;
if(s2>0)
{
t2=(struct TreeNode**)malloc(sizeof(struct TreeNode*)*s2);
if(t1[0]->left!=0)
t2[s++]=t1[0]->left;
if(t1[0]->right!=0)
t2[s]=t1[0]->right;
st(t1,t2,1,s2,k);
}
return root;
}
void st(struct TreeNode** t1,struct TreeNode** t2,int s1,int s2,int k)
{
int ss=2*s1;
struct TreeNode* po;
int ps=k%ss;
int psd2=ps/2;
struct TreeNode** t3;
int i=0;
if(ps)
{
t3=(struct TreeNode**)malloc(sizeof(struct TreeNode*)*ss);
while(i<ss)
{
if(i%2==0)
t3[i]=t1[i/2]->left;
else
t3[i]=t1[i/2]->right;
++i;
}
for(int j=0;j<ss;j++)
{
int lr=ps+j;
if(lr%2==0)
t1[(lr/2)%s1]->left=t3[j];
else
t1[(lr/2)%s1]->right=t3[j];
}
free(t3);
}
free(t1);
if(s2>0)
{
t1=(struct TreeNode**)malloc(sizeof(struct TreeNode*)*s2);
for(i=0;i<s2;i++)
t1[i]=t2[i];
free(t2);
s1=s2;
s2=0;
for(i=0;i<s1;i++)
{
if(t1[i]->left!=0)
++s2;
if(t1[i]->right!=0)
++s2;
}
i=0;
int sw2=0;
t2=(struct TreeNode**)malloc(sizeof(struct TreeNode*)*s2);
while(i<s1)
{
if(t1[i]->left!=0)
t2[sw2++]=t1[i]->left;
if(t1[i]->right!=0)
t2[sw2++]=t1[i]->right;
++i;
}
st(t1,t2,s1,s2,k);
}
}
C++ 解法, 执行用时: 40ms, 内存消耗: 9500KB, 提交时间: 2021-12-19
class Solution {
public:
TreeNode* cyclicShiftTree(TreeNode* root, int k) {
if(root == nullptr) return root;
vector<TreeNode*> parents {};
vector<TreeNode*> chilren {};
vector<int> slots {};
chilren.push_back(root);
while(true) {
// build
parents = chilren;
chilren.clear();
slots.clear();
for(int i = 0; i < parents.size(); i++){
auto parent = parents[i];
if(parent->left) {
chilren.push_back(parent->left);
slots.push_back(i*2+0);
}
if(parent->right) {
chilren.push_back(parent->right);
slots.push_back(i*2+1);
}
}
if(chilren.size() == 0) break; // all done
// doing
const auto N = (parents.size() * 2);
int shift = k % N;
if(shift == 0) continue; // done for this layer
for(const auto p: parents){
p->left = nullptr;
p->right = nullptr;
}
for(int i = 0; i < chilren.size(); i++){
auto index = (slots[i] + shift) % N;
auto p_index = index / 2;
auto left = index % 2 == 0;
auto parent = parents[p_index];
auto child = chilren[i];
if(left) {
parent->left = child;
} else {
parent->right = child;
}
}
}
return root;
}
};
/*
level max(2**level) actual slots
0 1 [1, max] 2*actual
|L:level| |C: max nodes| |R: actual nodes| S:slots
[0 - n] 2**L [1, C(L)] 2*R
k: >= 1 s: slot index
L C R S || 0 1 2 3 4 5
parent:
0 1 1 2 $
processing: shift: k % parent.S
1 2 2 $:0 $:1
*/
C++ 解法, 执行用时: 41ms, 内存消耗: 9484KB, 提交时间: 2021-12-09
/**
* 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类
*/
TreeNode* cyclicShiftTree(TreeNode* root, int k) {
// write code here
assert(k > 0);
if( !root ) return nullptr;
vector<vector<TreeNode *>> pTN_vec_vec( {{root}} );
queue<TreeNode *> pTN_queue( {root} );
while( !pTN_queue.empty() )
{
pTN_vec_vec.push_back( {} );
vector<TreeNode *> &pTN_vec = pTN_vec_vec.back();
int cnt = pTN_queue.size();
while( cnt-- )
{
TreeNode *pTN = pTN_queue.front(); pTN_queue.pop();
if( pTN->left ) pTN_queue.push( pTN->left );
if( pTN->right ) pTN_queue.push( pTN->right );
pTN_vec.push_back( pTN->left ); pTN_vec.push_back( pTN->right );
}
}
pTN_vec_vec.pop_back();
while(pTN_vec_vec.size() > 1)
{
vector<TreeNode *> &pTN_vec = pTN_vec_vec.back();
int len = pTN_vec.size(), shift = k%len;
if(shift){
shift = len-shift;
for(TreeNode *pTN : pTN_vec_vec[ pTN_vec_vec.size()-2 ])
if(pTN){
pTN->left = pTN_vec[shift++ % len];
pTN->right = pTN_vec[shift++ % len];
}
}
pTN_vec_vec.pop_back();
}
return root;
}
};
C++ 解法, 执行用时: 41ms, 内存消耗: 9592KB, 提交时间: 2022-01-28
/**
* 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类
*/
TreeNode* cyclicShiftTree(TreeNode* root, int k) {
//层序遍历，保存每一层包括空节点在内的所有节点
vector<vector<TreeNode*>> level;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
vector<TreeNode*> temp;
auto size = q.size();
while(size--) {
auto front = q.front();
q.pop();
temp.push_back(front);
if(front) {
q.push(front->left);
q.push(front->right);
}
}
level.push_back(std::move(temp));
}
level.pop_back();
//然后从最后一层开始移动
auto n = level.size();
for(int i=n-1;i>0;i--) {
auto size = level[i].size(); //当前第i层的元素个数
auto m = k % size; //得到等效的右移次数
//右移m次就是把最后m个元素放到数组最前面
vector<TreeNode*> f(level[i].begin(),level[i].begin()+size-m);
vector<TreeNode*> b(level[i].begin()+size-m,level[i].end());
int index = 0;
for(auto& node : b) {
level[i][index++] = node;
}
for(auto& node : f) {
level[i][index++] = node;
}
//重新挂载上一层的子节点
index = 0;
for(auto& node : level[i-1]) {
if(node) {
node->left = level[i][index++];
node->right = level[i][index++];
}
}
}
return root;
}
};
C++ 解法, 执行用时: 42ms, 内存消耗: 9984KB, 提交时间: 2021-12-20
/**
* 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类
*/
TreeNode* cyclicShiftTree(TreeNode* root, int k) {
// write code here
if(k == 0) return root;
vector<TreeNode*> arr;
vector<int> indexArr;
arr.push_back(root);
indexArr.push_back(0);
moveNode(arr, indexArr, k);
return root;
}
void moveNode(vector<TreeNode*> & arr,vector<int> & indexArr,int k){
vector<TreeNode*> a;
vector<int> index;
int count = 0;
for(TreeNode * node : arr){
if(node->left != nullptr){
a.push_back(node->left);
index.push_back(count);
node->left = nullptr;
}
count ++;
if(node->right != nullptr){
a.push_back(node->right);
index.push_back(count);
node->right = nullptr;
}
count ++;
}
if(a.size() == 0) return;
moveNode(a,index,k);
for(int i=0;i<a.size();i++){
int pindex = (index[i] + k)/2 % arr.size();
int isRight = (index[i] + k)%2;
TreeNode* parent = arr[pindex];
if(isRight){
parent->right = a[i];
}else{
parent->left = a[i];
}
}
}
};
个节点构成的二叉树，请你将每一层的节点向右循环位移
位。某层向右位移一位(即
)的含义为：