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

题解

题意整理：

基本题意

​ 给出一棵 $nn$ 个节点的二叉树，现在定义了二叉树的一次右平移操作，问二叉树右平移 $kk$ 次后长什么样。

数据范围

​ $1\le n\le 10^5,1\le k\le 1001\backslash le\; n\; \backslash le\; 10^5,\; 1\backslash le\; k\; \backslash le\; 100$ 。

右平移操作

​ 一次平移等价于如下过程：

​ 我们不妨设二叉树根的深度为 $11$ ，最大深度节点的深度为 $dd$ 。

​ 首先我们选中深度为 $d-1d-1$ 的所有节点，然后给他们的孩子指针从左到右标号（如图1）

​ 然后我们把标号后的节点的内容进行一轮平移，也就是让 $ii$ 号指针的内容变为原来 $i-1i-1$ 号指针的内容。特殊的，$11$ 号指针的内容变为原来最大号码指针的内容（如图2）。

​ 然后对深度为 $d-2d-2$ 的节点重复做类似的操作（图3）。

​ 然后是 $d-3,d-4d-3,d-4$ 深度，一直做这样的操作直到对深度 $11$ 的根节点做完此操作后停止，这便是二叉树的一次右平移操作。

解法1：直接模拟 $kk$ 次

分析与算法描述

​ 第一步： 用 $dd$ 个 vector 数组，按照从左到右的顺序存下每一层的节点。

​ 这个只需要进行一次 dfs 遍历二叉树就可以实现，遍历二叉树的时候维护一下当前递归的层数，即作为当前树节点的深度。注意遍历的时候先走左子节点，再去右子节点，才能保证对每一层的节点总是按照从左到右的相对顺序访问到。

​ 第二步： 从深度最大的vector数组开始，对每个数组的节点，把他们的指针进行一次右轮换。这样称为二叉树的一次右平移。

​ 第三步： 重复第二步的操作直到到达 $kk$ 次即可。

参考代码

#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)//对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) {
        // write code here
        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(nk)O(nk)$

​ 遍历二叉树是 $O(n)O(n)$ 的，将每个节点按层分类是 $O(n)O(n)$ 的。对整棵树做一次右平移操作是 $O(n)O(n)$ 的，我们做了 $kk$ 次操作，因此是 $O(nk)O(nk)$ 的。于是总时间复杂度 $O(nk)O(nk)$ 。

空间复杂度： $O(n)O(n)$

​ 二叉树本体的空间开销 $O(n)O(n)$ 。额外的空间开销来自于 vector 数组，因为最多只会 pushback $O(n)O(n)$ 的元素，因此空间复杂度 $O(n)O(n)$ 。于是总空间复杂度 $O(n)O(n)$ 。

解法2：把时间优化到 $O(n)O(n)$

分析与算法描述

​ 我们还是采用上面的算法，考虑如何优化时间。

​ 注意到层与层之间其实互不干扰，我们可以直接让一层的指针右轮换 $kk$ 次。

​ 假设轮换前指针的值分别是 $v_0,v_1,\mathrm{.}\mathrm{.}\mathrm{.}{v}_{m-1}v\_0,v\_1,...v\_\{m-1\}$ 轮换 $kk$ 次后指针的值分别是 $u_0,u_1,\mathrm{.}\mathrm{.}\mathrm{.}{u}_{m-1}u\_0,u\_1,...u\_\{m-1\}$ ，那么显然有 $u_{(i+k)\mathrm{m}\mathrm{o}\mathrm{d}m}=v_{i}u\_\{(i+k)\backslash bmod\; \backslash \; m\}\; =\; v\_i$ ，对所有的 成立。

​ 于是我们可以直接一步算出轮换 $kk$ 后的结果。

​ 要这么做，我们可以使用指针的指针，先把这些节点的左右孩子指针的地址抽离出来，放在一个叫做 tmp 的 vector 里面。此外我们再同步的求出 $vv$ 数组。接着，直接把 tmp 代表的一串地址当作我们要求得的 $uu$ 数组的地址，按照上面的关系计算出来就可以了。

参考代码

#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) {
        // write code here
        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)$

​ 遍历二叉树是 $O(n)O(n)$ 的，将每个节点按层分类是 $O(n)O(n)$ 的。对每层节点求其 $kk$ 次轮换的结果是 $O(n)O(n)$ 的。于是总时间复杂度 $O(n)O(n)$ 。

空间复杂度： $O(n)O(n)$

​ 二叉树本体的空间开销 $O(n)O(n)$ 。额外的空间开销来自于 vector 数组，因为最多只会 pushback $O(n)O(n)$ 的元素，因此空间复杂度 $O(n)O(n)$ 。于是总空间复杂度 $O(n)O(n)$ 。

​

​