/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) return root;
        queue<TreeNode*> my_que;
        my_que.push(root);
        while(my_que.empty() != 1)
        {
            int size = my_que.size();
            for(int i=0 ; i <size ;i++)
            {
                TreeNode* cur = my_que.front();
                my_que.pop();
                if(cur->left!= nullptr) my_que.push(cur->left);
                if(cur->right!= nullptr) my_que.push(cur->right);
        //交换左右子树
                if(cur->left!= nullptr || cur->right != nullptr)
                {
                    TreeNode* tem = cur->left;
                    cur->left = cur->right;
                    cur->right = tem;
                }
            }
        }
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void swap_tree_front(TreeNode* cur)
    {
        if(cur == nullptr) return;
        swap(cur->left , cur->right);
        swap_tree(cur->left);
        swap_tree(cur->right);
    }
   void swap_tree_middle(TreeNode* cur)
    {
        if(cur == nullptr) return;
        //这里中序是左中左，因为右被翻成左了
        swap_tree(cur->left);
        swap(cur->left , cur->right);
        swap_tree(cur->left);
    }
    void swap_tree_back(TreeNode* cur)
    {
        if(cur == nullptr) return;
        swap_tree(cur->left);
        swap_tree(cur->right);
        swap(cur->left , cur->right);
    }
    TreeNode* invertTree(TreeNode* root) {
        swap_tree_front(root);
        //swap_tree_middle(root);
        //swap_tree_back(root)
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void revers_tree(TreeNode* cur)
    {
        if(cur == nullptr) return;
        swap(cur->left , cur->right);
        revers_tree(cur->left);
        revers_tree(cur->right);
        return;
    }
    TreeNode* invertTree(TreeNode* root) {
        revers_tree(root);
        return root;
    }
};