题解 P5018 【对称二叉树】

高way · 2019-10-26 11:02:04 · 题解

主要思路同@koakuma，但使用结构数组实现。

#include <iostream>
using namespace std;
struct node{//w为权值，lc,rc为左右孩子
    short w;
    int lc,rc;
}n[100001];
int c;
void BuildTree(){//建一棵树
    int i,j,k;
    cin>>c;
    for(i=1;i<=c;i++){//记得从1开始标号，否则只有32分。
        cin>>n[i].w;
    }
    for(i=1;i<=c;i++){
        cin>>n[i].lc;
        cin>>n[i].rc;
    }
}
int NodeCount(int q){//其实就是后序遍历......
    int count=0;
    if(n[q].lc!=-1)count+=NodeCount(n[q].lc);//加上左子树的节点数
    if(n[q].rc!=-1)count+=nodeCount(n[q].rc);//加上右子树的节点数
    count++;//还有根节点
    return count;
}
bool IsBalance(int p,int q){
    if(p==-1&&q==-1)return true；//到底了
    if(p==-1||q==-1)return false;//不对称
    if(n[p].w!=n[q].w)return false;//权值不相等
    bool ans=(IsBalance(n[p].lc,n[q].rc)&&IsBalance(n[p].rc,n[q].lc));//外侧与内侧都要对称。
    return ans;
}
int main(){
    int i,j,k,max=0;
    BuildTree()；
    for(i=1;i<c;i++){
        if(IsBalance(n[i].lc,n[i].rc)){
            max=NodeCount(i)>max?NodeCount(i):max; 
        }
    }
    cout<<max<<endl;
    return 0;
}

为防被抄，已经在不明显的地方引入了编译错误与范围错误。