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

循环右移二叉树

题目描述

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

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

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

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

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

方法一：直接方法

解题思路

对于本题目的求解，首先我们用d(二叉树深度)个vector按照从左到右的顺序存下每一层的节点。然后从深度最大的vector开始，对每个vector中的节点进行右平移。最后按照深度递减的顺序，重复vector右移的操作，即可得到本题目的答案。

解题代码

class Solution {
public:
    vector <TreeNode*> layer[10000];   
    void dfs(TreeNode *x,int dep)//深度优先遍历二叉树
    {
        if(x==nullptr)return;
        layer[dep].push_back(x);//在对应深度的vector里面放入当前节点
        dfs(x->left,dep+1);
        dfs(x->right,dep+1);
    }
    
    void Shift(vector<TreeNode*> &vec)//对vector数组的节点进行一次指针右轮换
    {
        auto pre = vec[vec.size()-1]->right;//pre表示前一个节点的右儿子指针
        for(int i=0;i<vec.size();i++)
        {
            auto tmp = vec[i]->right;
            vec[i]->right = vec[i]->left;//当前节点的右儿子指针变为左儿子
            vec[i]->left = pre;//当前节点的做儿子指针变成前一个节点的右儿子
            pre = tmp; //记录当前节点的右儿子，准备给下一个节点使用
        }
    }
    
    TreeNode* cyclicShiftTree(TreeNode* root, int k) {
        dfs(root,1);
        for(int j=1;j<=k;j++)//一共做k次
            for(int i=MAXN-1;i>=1;i--)//对每一层的节点做一次右移
                if(layer[i].size())
                    Shift(layer[i]);
        
        return root;
    }
};

复杂度分析

时间复杂度：对二叉树进行右平移操作为$O(N)O(N)$,然后进行了k次，因此时间复杂度为$O(Nk)O(Nk)$

空间复杂度：vector长度为n，因此空间复杂度为$O(N)O(N)$

方法二：时间优化方法

解题思路

基于上述方法，我们发现在每一层进行右移操作时，是互不干扰的。因此，我们用一个vector来记录每层右移之后的地址(右移操作根据题目解释，循环右移即用取余操作来进行vector地址的保存)，这样便实现了对时间复杂度的优化。

解题代码

#define MAXN 100001
class Solution {
public:
    vector <TreeNode*> layer[MAXN];//存各层节点
    
    void dfs(TreeNode *x,int dep)//深度优先遍历二叉树
    {
        if(x==nullptr)return;
        layer[dep].push_back(x);//在对应深度的vector里面放入当前节点
        dfs(x->left,dep+1);
        dfs(x->right,dep+1);
    }
    
    void Shift(vector<TreeNode*> &vec,int k)//对vector数组的节点直接进行k次指针右轮换
    {
        vector<TreeNode **> tmp;
        vector<TreeNode *> v;
        for(auto &i: vec)
        {
            tmp.push_back(&(i->left));
            tmp.push_back(&(i->right));//tmp存好这些需要修改的值的地址
            v.push_back(i->left);
            v.push_back(i->right);//v表示轮换之前的指针值
        }
        for(int i=0;i<tmp.size();i++)
            *tmp[(i+k)%tmp.size()] = v[i];//按照轮换k次的结果直接更新指针的值
    }
    
    TreeNode* cyclicShiftTree(TreeNode* root, int k) {
        dfs(root,1);  
        for(int i=MAXN-1;i>=1;i--)//对每一层的节点做一次右移
            if(layer[i].size())
                Shift(layer[i],k);
        return root;
    }
};

复杂度分析

时间复杂度：对二叉树右移时间复杂度为$O(N)O(N)$，将k次优化为1次，因此时间复杂度仍为$O(N)O(N)$

空间复杂度：vector长度为n，因此空间复杂度为$O(N)O(N)$