C++LeetCode 구현(101.대칭 트 리 판단)

[LeetCode]101.대칭 트 리 판단 대칭 트 리
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
    1
/ \
2   2
/ \   / \
3  4 4  3
But the following is not:
    1
/ \
2   2
\   \
3    3
Note:
Bonus points if you could solve it both recursively and iteratively.
이 진 트 리 가 균형 트 리 인지 판단 합 니 다.예 를 들 어 두 개의 노드 n1,n2 가 있 습 니 다.우 리 는 n1 의 왼쪽 노드 의 값 과 n2 의 오른쪽 노드 의 값 이 같 는 지 비교 해 야 합 니 다.이 를 통 해 모든 좌우 두 노드 를 비교 해 야 합 니 다.우 리 는 재 귀 와 교체 두 가지 방법 으로 실현 할 수 있 고 쓰기 방법 이 다 르 지만 알고리즘 핵심 은 모두 같다.
해법 1:

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if (!root) return true;
        return isSymmetric(root->left, root->right);
    }
    bool isSymmetric(TreeNode *left, TreeNode *right) {
        if (!left && !right) return true;
        if (left && !right || !left && right || left->val != right->val) return false;
        return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
    }
    
};

교체 쓰기 방법 은 두 개의 대기 열 quue 를 통 해 이 루어 져 야 합 니 다.우 리 는 먼저 빈 것 을 판단 하고 루트 가 비어 있 으 면 true 로 돌아 갑 니 다.그렇지 않 으 면 루트 의 좌우 두 개의 키 노드 를 각각 두 개의 대기 열 에 불 러 오고 순환 을 시작 합 니 다.순환 조건 은 두 개의 대기 열 이 모두 비어 있 지 않 습 니 다.while 순환 에서 우 리 는 먼저 두 대열 의 첫 번 째 요 소 를 각각 꺼 냈 다.만약 에 두 개가 모두 빈 노드 라면 바로 건 너 뛰 었 다.왜냐하면 우 리 는 아직 비교 가 끝나 지 않 았 기 때문에 어떤 노드 에 왼쪽 노드 가 없 을 수도 있 지만 오른쪽 노드 는 여전히 존재 하기 때문에 여기 서 계속 할 수 밖 에 없다.그리고 다시 보면 하 나 는 비어 있 고 다른 하 나 는 비어 있 지 않 으 면 이때 대칭 성 이 파괴 되 었 고 더 이상 비교 하지 않 고 false 로 돌아 갑 니 다.만약 에 두 개의 결점 이 모두 존재 하지만 그 결점 값 이 다 르 면 대칭 성 을 파괴 하고 false 로 돌아간다.그렇지 않 으 면 node 1 의 왼쪽 노드 와 오른쪽 노드 를 대기 열 1 에 배열 합 니 다.node 2 의 오른쪽 노드 와 왼쪽 노드 를 대기 열 2 에 배열 하고 순서 에 대한 대응 문 제 를 주의 하 십시오.마지막 순환 이 끝 난 후에 true 로 돌아 갑 니 다.여 기 는 두 대기 열 이 동시에 비어 있 는 지 확인 할 필요 가 없습니다.순환 이 끝 난 후에 두 대기 열 이 모두 비어 있 을 수 있 기 때 문 입 니 다.다른 상황 은 예 를 들 어 비어 있 지 않 고 순환 내부 에서 false 로 돌아 갑 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        queue<TreeNode*> 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;
    }
};

참고 자료:
https://leetcode.com/problems/symmetric-tree/
https://leetcode.com/problems/symmetric-tree/discuss/33054/Recursive-and-non-recursive-solutions-in-Java
C++구현 LeetCode(101.판단 대칭 트 리)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 판단 대칭 트 리 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 부탁드립니다!