c 언어 판단 두 갈래 트리 대칭 귀속 여부

4553 단어 알고리즘 문제
힘단추 문제 - 두 갈래 나무가 거울로 대칭적인지 판단한다.
사고방식: p는 루트의 왼쪽 아이를 가리키고 q는 루트의 오른쪽 아이를 가리킨다.p와 q의 값이 같은지 아닌지를 판단하면 p의 왼쪽 아이와 q의 오른쪽 아이가 같은지, p의 오른쪽 아이와 q의 왼쪽 아이가 같은지, 같은지 판단하면 계속 귀속된다.p와 q가 모두 비어 있을 때, 전체 두 갈래 나무가 이미 다 훑어보았고, 훑어보는 과정에서 p와 q의 값이 계속 같다면true로 돌아간다.주어진 두 갈래 나무의 구조는 다음과 같다.
struct TreeNode 
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};
bool fun(struct TreeNode* p,struct TreeNode* q)
{    
    if(NULL==p&&NULL==q) return true;
    if(NULL==p||NULL==q) return false;
    if(p->val!=q->val) return false;
    bool L=fun(p->left,q->right);
    bool R=fun(p->right,q->left);
    return L&&R;
}
bool isSymmetric(struct TreeNode* root)
{    
    if(NULL==root) return true;
    struct TreeNode *p=root->left;
    struct TreeNode *q=root->right;
    return fun(p,q);
}

좋은 웹페이지 즐겨찾기