力扣（LeetCode）226. 翻转二叉树

思路：
从首节点开始，如果首节点为空则直接返回，否则交换左右子树，然后递归下一层
PS：本来用swap函数就可以解决，不过我还是自己写个Swap，权当练习指针操作，可以使用指针的指针，也可以对取指针的地址，然后再用指针进行交换（对指针操作比较迷的话，就直接用swap函数，干净利落）

#include<iostream>
#include<cstdlib>
using namespace std;

typedef struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
} TreeNode,*SearchTree,*Position;

void PreOrderTraversal(SearchTree T)
{
    if(T==NULL)
        return;
    cout<<T->val<<" ";
    PreOrderTraversal(T->left);
    PreOrderTraversal(T->right);
}

SearchTree Insert(int val,SearchTree T)
{
    if(T==NULL)
    {
        T = (SearchTree)malloc(sizeof(TreeNode));
        if(T==NULL)
        {
            cout<<"MALLOC ERROR\n"<<endl;
            exit(1);
        }
        T->val = val;
        T->left = T->right = NULL;
    }
    else
    {
        if(val>T->val)
            T->right = Insert(val,T->right);
        else if(val<T->val)
            T->left = Insert(val,T->left);
    }
    return T;
}

class Solution
{
public:
    void Swap(TreeNode **A,TreeNode **B)
    {
        TreeNode *temp = *A;
        *A = *B;
        *B = temp;
    }
    TreeNode* invertTree(TreeNode* root)
    {
        if(root==NULL)
            return NULL;
        Swap(&root->left,&root->right);
//        swap(root->left,root->right);
        root->left = invertTree(root->left);
        root->right = invertTree(root->right);

        return root;
    }
};

//class Solution
//{
//public:
//    void Swap(TreeNode *&A,TreeNode *&B)
//    {
//        TreeNode *temp = A;
//        A = B;
//        B = temp;
//    }
//    TreeNode* invertTree(TreeNode* root)
//    {
//        if(root==NULL)
//            return NULL;
//        Swap(root->left,root->right);
////        swap(root->left,root->right);
//        root->left = invertTree(root->left);
//        root->right = invertTree(root->right);
//
//        return root;
//    }
//};

int main()
{

    Solution s;
    SearchTree T1 = NULL;
    SearchTree T2 = NULL;

    T1 = Insert(4,T1);
    T1 = Insert(2,T1);
    T1 = Insert(7,T1);
    T1 = Insert(1,T1);
    T1 = Insert(3,T1);
    T1 = Insert(6,T1);
    T1 = Insert(9,T1);



    PreOrderTraversal(T1);
    cout<<endl;

    T2 = s.invertTree(T1);
    PreOrderTraversal(T2);

    return 0;
}