NC543 魔力转圈圈

描述

给你一个二叉树和一个操作序列，要求你根据操作序列对二叉树的某个子树做镜像操作，$mm$次操作之后，求得操作后的中序序列。

1. 直接模拟

本题是二叉树镜像的升级, 最暴力的做法是直接按题意模拟，对每个操作执行一遍，再中序遍历。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 魔力转圈圈
     * @param n int整型 
     * @param m int整型 
     * @param l int整型vector 
     * @param r int整型vector 
     * @param k int整型vector 
     * @return int整型vector
     */
    vector<int> res;
    
    // 对l和r描述的二叉树的node号节点翻转
    void rotate(vector<int> &l, vector<int> &r, int node) {
        if (!node) return;
        // 数组下标从0开始，节点从1开始，减1修正
        node--;
        
        swap(l[node], r[node]);
        rotate(l, r, l[node]);
        rotate(l, r, r[node]);
    }

    // 求中序遍历，当前节点是node           
    void inorder(vector<int> &l, vector<int> &r, int node = 1) {
        if (node) {
            inorder(l, r, l[node-1]);
            res.push_back(node);
            inorder(l, r, r[node-1]);
        }
    }
    vector<int> solve(int n, int m, vector<int>& l, vector<int>& r, vector<int>& k) {
        for (auto i : k) {
            rotate(l, r, i);
        }
        
        inorder(l, r);
        return res;
    }
};

• 时间复杂度：$O(mn)O(mn)$, m次操作，每次操作遍历了节点为$nn$的二叉树。

• 空间复杂度：$O(n)O(n)$, 存储中序序列用了长度为$nn$的数组，递归深度最大也为$nn$

2. 优化

$n,mn,m$的级别都高达$10^{5}10^5$, 思路一肯定是错误的，我们看下优化的办法。观察到旋转是具有对称性的，旋转2次相当于不变。

因此我们可以用类似于线段树的lazy tag的思路，用一个$cntcnt$数组维护下每个节点被操作了多少次，如果是偶数次直接不用管，如果是奇数次，则交换过程中下放标记，即对左右儿子的操作次数+1.

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 魔力转圈圈
     * @param n int整型 
     * @param m int整型 
     * @param l int整型vector 
     * @param r int整型vector 
     * @param k int整型vector 
     * @return int整型vector
     */
    vector<int> res;
    unordered_map<int, int> lazy;
    
    void rotate(vector<int>& l, vector<int>& r, int node) {
        if (!node) return;
        if (lazy[node] % 2 == 1) {
            lazy[l[node-1]]++, lazy[r[node-1]]++;

            swap(l[node-1], r[node-1]);
        }
        
        // rotate操作也相当于pushdown，所以即使cnt是偶数也要向下递归，只是不翻转了
        rotate(l, r, l[node-1]);
        rotate(l, r, r[node-1]);
    }
    
    void inorder(vector<int> &l, vector<int> &r, int node = 1) {
        if (node) {
            inorder(l, r, l[node-1]);
            res.push_back(node);
            inorder(l, r, r[node-1]);
        }
    }
    
    vector<int> solve(int n, int m, vector<int>& l, vector<int>& r, vector<int>& k) {
        for (int i : k) {
            lazy[i]++;
        }
        
        rotate(l, r, 1);
        inorder(l, r);
       
        return res;
    }
};

• 时间复杂度：$O(m+n)O(m+n)$, m次操作记录lazy标记，只对树遍历了一遍。

• 空间复杂度：$O(n)O(n)$, 存储中序序列用了长度为$nn$的数组，递归深度最大也为$nn$，还存储了lazy序列，最大长度也可能为$nn$.