매일 하나의 알고리즘 문제-대칭 두 갈래 나무

제목:

두 갈래 나무를 정해서 거울이 대칭적인지 확인하세요.
예를 들어 두 갈래 나무[1,2,2,3,4,3]는 대칭적이다.

  	1
   / \
  2   2
 / \ / \
3  4 4  3

그러나 아래 이것[1,2,2,null,3,null,3]은 거울의 대칭이 아니다.

 	1
   / \
  2   2
   \   \
   3    3

설명:
만약 네가 귀속과 교체 두 가지 방법을 운용하여 이 문제를 해결할 수 있다면, 매우 가산점이 있을 것이다.

답변:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


bool isSymmetric(struct TreeNode* root){
    if(root==NULL) return true;
    return fun(root->left,root->right);
}

int fun(struct TreeNode* l_root,struct TreeNode* r_root)
{
    if(l_root==NULL&&r_root==NULL) return true;// ， true
    if(l_root==NULL||r_root==NULL) return false;// ， ， false
    
    return (l_root->val==r_root->val)&&fun(l_root->left,r_root->right)
    &&fun(l_root->right,r_root->left);
}

문제 해결 방법:

만약 나무의 왼쪽 나무와 오른쪽 나무의 거울이 대칭적이라면, 이 나무는 대칭적이다.
따라서 이 문제는 두 나무가 어떤 상황에서 서로 거울이 되는가?
다음 조건을 모두 충족하면 두 트리가 서로 대칭복사됩니다.
1. 그것들의 두 뿌리 결점은 같은 값을 가지고 있다.2. 각 나무의 오른쪽 하위 트리는 다른 나무의 왼쪽 하위 트리와 대칭됩니다.
사람이 거울 앞에 서서 자신을 바라보는 것처럼.거울 속의 반사는 현실 속의 사람과 같은 머리를 가지지만 반사된 오른팔은 사람의 왼팔에 대응한다. 반대로도 마찬가지다.
귀속 방법: return(l_root->val=r_root->val) & fun(l_root->left, r_root->right) & fun(l_root->right, r_root->left);1. 뿌리 노드의 좌우 서브 트리를 만족시키기 2.왼쪽 나무를 만족시키는 왼쪽 나무는 오른쪽 나무의 오른쪽 나무와 같다.왼쪽 나무의 오른쪽·자나무와 오른쪽 자나무의 왼쪽 자나무가 같다는 것을 만족시키다