[LeetCode] 951. Flip Equivalent Binary Trees

https://leetcode.com/problems/flip-equivalent-binary-trees/?envType=daily-question&envId=2024-10-24

leetcode - Flip Equivalent Binary Trees

문제 유형: 이진트리, bfs, dfs, 재귀

문제 난이도: Medium

 

문제

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.

A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.

Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivalent or false otherwise.

 

이진트리 T에 대해서, flip연산을 다음과 같이 정한다: 아무 노드를 정해서 왼쪽과 오른쪽 서브트리를 바꾼다.

이진트리 X는 X에 flip연산을 몇 번이고 적용시켜서 Y와 같아질 수 있고 오직 그럴 때에만 이진트리 Y와 flip-동치한다고 한다.

두 개의 이진트리 root1과 root2가 주어진다.

두 트리가 flip-동치이면 true를, 아니면 false를 반환하시오.

 

풀이

우선, 공통의 base-case는 다음과 같다:

현재 서브트리의 루트가 둘다 null이라면, flip-동치이다.

둘 중 하나만 null이라면, flip-동치가 아니다.

두 루트의 값이 다르다면, flip-동치가 아니다.

 

bfs를 이용한 풀이 - 플립이 어떻게 일어나던, 부모-자식관계만 동일하면 상관없다.

즉, 두 트리의 부모-자식관계를 확인하기 위해서 parent[]배열을 만든다. 

parent[i] = 노드 i의 부모노드 키이다.

둘다 bfs를 해주면서 부모자식관계를 저장한 뒤, 순차적으로 parent를 비교해주면 된다.

 

dfs를 이용한 풀이 - 서브트리는 뒤집어지거나, 뒤집어지지 않거나다.

즉, flipEquiv(트리1의 왼쪽서브트리, 트리2의 왼쪽서브트리) && flipEquiv(트리1의 오른쪽서브트리, 트리2의 오른쪽서브트리)와

flipEquiv(트리1의 왼쪽서브트리, 트리2의 오른쪽서브트리) && flipEquiv(트리1의 오른쪽서브트리, 트리2의 왼쪽서브트리)의 or값을 리턴하면 된다.

이러면, base-case에 의해서 정확한 답이 나온다.

각 서브트리에 대해, 뒤집어져있던 아니건 둘 중 하나라도 맞다면 flip-equivalent란 뜻이고, 루트가 같고 하위 서브트리들도 서로 flip-equivalent하면 두 트리는 flip-equivalent하다.

 

코드

C++

BFS를 이용한 풀이

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        if(root1 == nullptr && root2 == nullptr) return true;
        if(root1 == nullptr || root2 == nullptr) return false;
        if(root1 -> val != root2 -> val) return false;
        q1.push(root1);
        q2.push(root2);

        vector<int> parents1(100, 100);
        vector<int> parents2(100, 100);

        while(!q1.empty() && !q2.empty()) {
            int q1Size = q1.size();
            int q2Size = q2.size();

            if(q1Size != q2Size) return false;
            for(int i = 0; i < q1Size; ++i) {
                auto t1Node = q1.front();
                q1.pop();

                auto t2Node = q2.front();
                q2.pop();

                if(t1Node -> left) {
                    q1.push(t1Node -> left);
                    parents1[t1Node -> left -> val] = t1Node -> val;
                }
                if(t1Node -> right) {
                    q1.push(t1Node -> right);
                    parents1[t1Node -> right -> val] = t1Node -> val;
                }
 
                if(t2Node -> left) {
                    q2.push(t2Node -> left);
                    parents2[t2Node -> left -> val] = t2Node -> val;
                }
                if(t2Node -> right) {
                    q2.push(t2Node -> right);
                    parents2[t2Node -> right -> val] = t2Node -> val;
                }
            }
        }

        for(int i = 0; i < 100; ++i) {
            if(parents1[i] != parents2[i]) return false;
        }

        return true;
    }
};

 

DFS를 이용한 풀이

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr && root2 == nullptr) return true;
        if(root1 == nullptr || root2 == nullptr) return false;
        if(root1 -> val != root2 -> val) return false;

        bool noflip = flipEquiv(root1 -> left, root2 -> left) && flipEquiv(root1 -> right, root2 -> right);
        bool flip = flipEquiv(root1 -> left, root2 -> right) && flipEquiv(root1 -> right, root2 -> left);

        return noflip || flip;
    }
};