#include <iostream>

using namespace std;


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) return root;
        TreeNode* left = invertTree(root->left); //翻转左子树
        TreeNode* right = invertTree(root->right); //翻转右子树
        root->left = right;
        root->right = left;
        return root;
    }
};

//创建二叉树
TreeNode* createBinaryTree() {
    TreeNode* root = new(TreeNode);
    TreeNode* p1 = new(TreeNode);
    TreeNode* p2 = new(TreeNode);
    TreeNode* p3 = new(TreeNode);
    TreeNode* p4 = new(TreeNode);
    TreeNode* p5 = new(TreeNode);
    TreeNode* p6 = new(TreeNode);

    root->left = p1;
    root->right = p2;
    root->val = 4;

    p1->left = p3;
    p1->right = p4;
    p1->val = 2;

    p2->left = p5;
    p2->right = p6;
    p2->val = 7;

    p3->left = nullptr;
    p3->right = nullptr;
    p3->val = 1;

    p4->left = nullptr;
    p4->right = nullptr;
    p4->val = 3;

    p5->left = nullptr;
    p5->right = nullptr;
    p5->val = 6;

    p6->left = nullptr;
    p6->right = nullptr;
    p6->val = 9;
    return root;
}

//先序遍历二叉树
void print(TreeNode* root) {
    if(!root) return;
    cout<<root->val<<" ";
    print(root->left);
    print(root->right);
}

int main()
{
    Solution obj;
    TreeNode* root = createBinaryTree();
    obj.invertTree(root);
    print(root);
    cout<<endl;
    return 0;
}