题意：
        一个以1为根结点的n个结点的二叉树，对这颗二叉树进行m次旋转。

        每次旋转会指定一个结点，并让以这个结点为根的子树中的所有结点的左右儿子互换。

        m次操作之后，以中序遍历的方式输出操作完之后的二叉树。


方法一：
递归

思路：
        直接模拟。
       对于每次操作， 都递归的以这个结点为根的子树中的所有结点的左右儿子互换。
        最后，递归的中序遍历返回答案。



class Solution {
public:
    vector<int> res;//中序遍历序列
    vector<int> solve(int n, int m, vector<int>& l, vector<int>& r, vector<int>& k) {
        for(int i=0;i<m;i++){
          dfs(k[i],l,r);//每次旋转操作
        }
        inOrder(1,l,r);//中序遍历
        return res;
    }
    
    void dfs(int x,vector<int>& l, vector<int>& r){
        if(x==0)//如果遇到空节点，返回
            return;
        dfs(l[x-1],l,r);//递归左儿子
        dfs(r[x-1],l,r);//递归右儿子
        swap(l[x-1],r[x-1]);//交换左右儿子节点
    }
    
    void inOrder(int x,vector<int>& l, vector<int>& r){
        if(x==0)
            return;
        inOrder(l[x-1],l,r);//递归左儿子
        res.push_back(x);
        inOrder(r[x-1],l,r);//递归左儿子

    }
    
};
时间复杂度：
空间复杂度：

方法二：
递归优化

思路：
        关键点：同一个节点被操作两遍，等效于无操作。
        用数组存储每个节点被操作的次数。
        
        如果操作数是奇数，则交换左右儿子节点，并将左右儿子节点的操作数加一，就这样一层一层深入。
        
 

class Solution {
public:
    vector<int> res;//中序遍历序列
    vector<int> solve(int n, int m, vector<int>& l, vector<int>& r, vector<int>& k) {
        vector<int> cnt(n+1);//存储每个节点被操作的次数
        for(int i=0;i<m;i++){
            cnt[k[i]]++;
        }
        
        dfs(1,l,r,cnt);//一次递归
        inOrder(1,l,r);//中序遍历
        return res;
    }
    
    void dfs(int x,vector<int>& l, vector<int>& r,vector<int> cnt){
        if(x==0)//如果遇到空节点，返回
            return;
        if(cnt[x]%2==1){//如果操作数是奇数，则交换左右儿子节点，并将左右儿子节点的操作数加一
          cnt[l[x-1]]++;
          cnt[r[x-1]]++;
          swap(l[x-1],r[x-1]);
        }
        dfs(l[x-1],l,r,cnt);//递归左儿子
        dfs(r[x-1],l,r,cnt);//递归右儿子
    }
    
    void inOrder(int x,vector<int>& l, vector<int>& r){
        if(x==0)//如果遇到空节点，返回
                    return;
        inOrder(l[x-1],l,r);//递归左儿子
        res.push_back(x);
        inOrder(r[x-1],l,r);//递归左儿子
    }
    
};

时间复杂度：
空间复杂度：