7-3树的同构(C++)

本题来自PTA, https://pintia.cn/problem-sets/15/problems/711

题目

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。

现给定两棵树，请你判断它们是否是同构的。

我现在在看慕课上浙江大学的《数据结构》课程，此次代码不如课堂上何钦铭老师给出的好，但是是自己课后独立完成，还是很开心的

代码如下

#include <iostream>

using namespace std;

typedef struct PNode* List;     //定义结构指针
struct PNode                    //定义结构点
{
    char c;
    PNode* left;
    PNode* right;
};

List BuideTree();               //构建树
void CompareTree(List tree1, List tree2, int& refFlag);  //同构比较

int main()
{
    List tree1, tree2;       //要比较的两个树
    int flag = 1;            //默认同构，若不同构则复位
    int& refFlag = flag;     //定义比较结果标志位
    tree1 = BuideTree();
    tree2 = BuideTree();
    CompareTree( tree1, tree2, refFlag);
    if (flag)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

/**构建树*/
List BuideTree()
{
    int num;
    cin >> num;
    if(num)    //树的结点树大于0，则构建树，否则返回空指针
    {
        List ptrNode[num] = {NULL};
        char leftNum[num], rightNum[num];
        for (int i = 0; i < num; ++i)    //创建num个结点
        {
            List T;
            T = new PNode;
            ptrNode[i] = T;
        }
        for (int i = 0; i < num; ++i)            //写入数据
        {
            cin >> ptrNode[i]->c;                //结点数据
            cin >> leftNum[i] >> rightNum[i];    //对应结点左儿子和右儿子
        }
        for (int i = 0; i < num; ++i)            //将结点链接起来，成为二叉树
        {
            if (leftNum[i] == '-')
            {
                ptrNode[i]->left = NULL;
            }
            if (rightNum[i] == '-')
            {
                ptrNode[i]->right = NULL;
            }
            if ( leftNum[i]!= '-' )
            {
                ptrNode[i]->left = ptrNode[leftNum[i]-48];
            }
            if (rightNum[i] != '-')
            {
                ptrNode[i]->right = ptrNode[rightNum[i]-48];
            }
        }
        //检测谁是根
        int root = 0;
        int sum = 0, sumTotal = 45*(num+1);       //将所有儿子对应的数字相加得到sum，总的sumTotal - sum得到根对应的数字
        for (int i = 0; i < num; ++i)
        {
            sum += leftNum[i];
            sum += rightNum[i];
            sumTotal += i;
            sumTotal += 48;
        }
        root = sumTotal - sum - 48;
        return ptrNode[root];
    }
    else
    {
        return NULL;
    }
}

/**树的同构检测*/
void CompareTree(List tree1, List tree2, int& refFlag)
{
    if( !tree1 && !tree2)  //皆为空
    {
        return;
    }
    else if ( tree1 && tree2 )
    {
        if ( tree1->c == tree2->c )
        {
           if (!tree1->left && !tree2->left)
           {
               CompareTree(tree1->right, tree2->right, refFlag);
           }
           else if ( !tree1->right && !tree2->right )
           {
               CompareTree(tree1->left, tree2->left, refFlag);
           }
           else if ( !tree1->right && !tree2->left )
           {
               CompareTree(tree1->left, tree2->right, refFlag);
           }
           else if ( !tree1->left && !tree2->right )
           {
               CompareTree(tree1->right, tree2->left, refFlag);
           }
           else if ( tree1->right && tree1->left && tree2->right && tree2->left )
           {
               if (tree1->right->c == tree2->right->c && tree1->left->c == tree2->left->c)
               {
                   CompareTree(tree1->right, tree2->right, refFlag);
                   CompareTree(tree1->left, tree2->left, refFlag);
               }
               else if (tree1->right->c == tree2->left->c && tree1->left->c == tree2->right->c)
               {
                   CompareTree(tree1->right, tree2->left, refFlag);
                   CompareTree(tree1->left, tree2->right, refFlag);
               }
               else
               {
                   refFlag = 0;
               }
           }
           else
           {
               refFlag = 0;
           }
        }
        else
        {
            refFlag = 0;
        }
    }
    else
    {
        refFlag = 0;
    }
}

第一次写博客，好像不知道写什么哎。。。