题解 | #魔力转圈圈#

思路：

题目的主要信息：

一个二叉树根节点为1，l与r分别记录树的左右子节点，其中第 $i$ 个对应节点为 $i$ 的左右子节点
k数组中记录将要旋转的节点，旋转的时候将其所有子树及其子节点都交换位置
最后输出的数组为二叉树的中序遍历
0表示空节点

方法一：递归
具体做法：
利用递归的思想，遍历每一个要旋转的节点，将其子节点交换位置，并递归交换子节点的子节点。需要注意的是，如果一个节点被交换了两次，那么相当于没有被交换，因此我们用一个数组统计交换次数，如果次数为奇数，我们交换一次，次数为偶数，我们不交换。
图片说明
最后递归中序遍历（左根右）输出。

class Solution {
public:
    void rotate(int t, vector<int> &l, vector<int> &r, vector<int>& cnt){
        if(cnt[t] % 2 == 1){ //偶数不转奇数转1次
            swap(l[t - 1], r[t - 1]);
            cnt[l[t - 1]]++; //子树的次数也要增加
            cnt[r[t - 1]]++;
        }
        if(l[t - 1] != 0)
            rotate(l[t - 1], l, r, cnt); 
        if(r[t - 1] != 0)
            rotate(r[t - 1], l, r, cnt);
        return;
    }
    void inOrder(int t, vector<int> &l, vector<int> &r, vector<int>& res){ //中序输出
        if(l[t - 1] != 0)
            inOrder(l[t - 1], l, r, res); //递归找左子树
        res.push_back(t);
        if(r[t - 1] != 0) 
            inOrder(r[t - 1], l, r, res); //递归找右子树
        return;
    }
    vector<int> solve(int n, int m, vector<int>& l, vector<int>& r, vector<int>& k) {
        vector<int> res;
        vector<int> cnt(n + 1, 0);
        for(int i = 0; i < k.size(); i++)
            cnt[k[i]]++; //某个节点要转的次数
        rotate(1, l, r, cnt);
        inOrder(1, l, r, res);
        return res;
    }
};

复杂度分析：

时间复杂度： $O(m+n)$ ，遍历k数组为 $O(m)$ ，中序输出为 $O(n)$ ，旋转是 $O(n)$
空间复杂度： $O(n)$ ，递归栈最大深度及辅助数组cnt

方法二：非递归
具体做法：
对于二叉树的问题，能用递归解决一般也可以用栈来辅助，使用非递归，旋转时需要先将子问题加入栈中，再交换。输出时每次需要找到最左子节点，再访问根，再访问右节点。

class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& l, vector<int>& r, vector<int>& k) {
        vector<int> res;
        vector<int> cnt(n + 1, 0);
        for(int i = 0; i < k.size(); i++)
            cnt[k[i]]++; //某个节点要转的次数
        stack<int> s;
        s.push(1);
        while(!s.empty()){  //旋转
            int index = s.top() - 1;
            s.pop();
            if(l[index] != 0){   //左子树
                cnt[l[index]] += cnt[index + 1];
                s.push(l[index]);
            }
            if(r[index] != 0){ //右子树
                cnt[r[index]] += cnt[index + 1];
                s.push(r[index]);
            }
            if(cnt[index + 1] % 2 == 1){ //偶数不交换，奇数交换一次
                swap(l[index], r[index]);
            }
        }
        vector<bool> vis(n + 1, false); //记录是否访问过
        s.push(1);
        int index = 0;
        while(!s.empty()){  //非递归中序遍历
            int root = s.top();
            if(!vis[root] && l[root - 1] != 0){ //没有访问过，且左节点存在
                s.push(l[root - 1]);
                vis[root] = true;
                continue;
            }
            s.pop();
            res.push_back(root);
            index++; 
            if(r[root - 1] != 0)  //右子树
                s.push(r[root - 1]);
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(m+n)$ ，遍历k数组为 $O(m)$ ，中序输出为 $O(n)$ ，旋转是 $O(n)$
空间复杂度： $O(n)$ ，栈最大空间及辅助数组cnt