1. 제목 설명

두 갈래 나무를 정해서 거울이 대칭적인지 확인하세요.
예를 들어 두 갈래 나무[1,2,2,3,4,3]는 대칭적이다.
1/\2 2/\/\3 4 3 하지만 아래 이것 [1, 2, null, 3, null, 3] 은 미러 대칭이 아닙니다.
1/\2 2\3 설명:
만약 네가 귀속과 교체 두 가지 방법을 운용하여 이 문제를 해결할 수 있다면, 매우 가산점이 있을 것이다.

2. 문제풀이 사고방식

검지 offer 해법:
루트-오른쪽 아이-왼쪽 아이, 먼저 루트(루트-왼쪽 아이-오른쪽 아이) 결과와 일치하면 대칭적인 새로운 루트 방식을 정의합니다.중간 노드가 충족되지 않으면 False로 돌아갑니다.
반복법:
반복 쓰기는 두 개의 대기열queue를 빌려 이루어져야 합니다. 우선 공백을 판정하고 루트가 비어 있으면true로 되돌아갑니다.그렇지 않으면 루트의 좌우 두 개의 하위 결점을 각각 두 개의 대기열에 불러오고 순환을 시작합니다. 순환 조건은 두 개의 대기열이 비어 있지 않습니다.while 순환에서 우리는 먼저 두 대열의 첫 번째 요소를 각각 꺼낸다. 만약에 두 개가 모두 빈 결점이라면 바로 건너뛴다. 왜냐하면 우리는 아직 비교가 끝나지 않았기 때문에 어떤 결점이 왼쪽 결점이 없을 수도 있지만 오른쪽 결점은 여전히 존재하기 때문에 여기는continue만 있을 수 있다.그리고 다시 보면 하나가 비어 있고 다른 하나가 비어 있지 않으면 대칭성은 이미 파괴되어 더 이상 비교할 필요가 없다. 바로false로 돌아간다.만약 두 결점이 모두 존재하지만 그 결점 값이 다르면 이것은 대칭성을 파괴하고false로 돌아간다.그렇지 않으면node1의 왼쪽 결점과 오른쪽 결점을 대기열 1로 배열하고, 여기에서 node2의 오른쪽 결점과 왼쪽 결점을 대기열 2로 배열하고, 순서에 대한 문제를 주의해야 한다.마지막으로 순환이 끝난 후true로 돌아갑니다. 여기는 두 개의 대기열이 동시에 비어 있는지 확인할 필요가 없습니다. 순환이 끝난 후에는 두 개의 대기열이 모두 비어 있는 상황일 수 있기 때문입니다. 다른 상황, 예를 들어 텅 비어 있지 않으면 순환 내부에서false로 돌아옵니다.

3. 코드 구현

버전 1

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def dfs(self,root1,root2):
        if not root1 and not root2:
            return True
        if (root1 and not root2) or (root2 and not root1) or root1.val!=root2.val:
            return False
        res1=True
        res2=True
        res1=self.dfs(root1.left, root2.right)
        res2=self.dfs(root1.right, root2.left)
        return res1 and res2
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.dfs(root,root)

버전 2(간결하게):

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def dfs(self,root1,root2):
        if not root1 and not root2:
            return True
        if not root1 or not root2 or root1.val!=root2.val:
            return False
        res1=self.dfs(root1.left, root2.right)
        res2=self.dfs(root1.right, root2.left)
        return res1 and res2
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.dfs(root,root)

또 다른 좋은 실현:

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isSame(self,r1,r2):
        if not r1 and not r2:
            return True
        if not r1:
            return False
        if not r2:
            return False
        if r1.val!=r2.val:
            return False
        return self.isSame(r1.left,r2.right) and self.isSame(r1.right,r2.left)
    def isSymmetrical(self, pRoot):
        # write code here
        return self.isSame(pRoot,pRoot)
        

반복법(C++):

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        queue q1, q2;
        q1.push(root->left);
        q2.push(root->right);
        while (!q1.empty() && !q2.empty()) {
            TreeNode *node1 = q1.front(); q1.pop();
            TreeNode *node2 = q2.front(); q2.pop();
            if (!node1 && !node2) continue;
            if((node1 && !node2) || (!node1 && node2)) return false;
            if (node1->val != node2->val) return false;
            q1.push(node1->left);
            q1.push(node1->right);
            q2.push(node2->right);
            q2.push(node2->left);
        }
        return true;
    }
};