[코테연습] 951. Flip Equivalent Binary Trees

- 트리 / 이진트리 / DFS 문제

 

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

 

- 문제분석

 

• 기본 아이디어:
  • 재귀적으로 트리의 각 노드를 비교하여, 두 노드가 서로 플립을 통해 같아질 수 있는지 확인합니다.
  • 두 노드가 같아지기 위해서는 다음 두 가지 조건 중 하나가 만족해야 합니다:
    1. 자식 노드들이 동일한 위치에 있어야 함 (즉, 왼쪽-왼쪽, 오른쪽-오른쪽).
    2. 자식 노드들이 플립하여 동일한 모양이 될 수 있어야 함 (즉, 왼쪽-오른쪽, 오른쪽-왼쪽).
• 재귀적인 접근:
  • 두 트리의 루트가 **둘 다 None**이면 같은 트리입니다.
  • 하나의 루트만 None이거나 두 루트의 값이 다르면, 두 트리는 다릅니다.
  • 그렇지 않다면, 자식들을 비교합니다:
    • 두 가지 경우를 비교해야 합니다.
      1. root1.left와 root2.left가 같고, root1.right와 root2.right가 같음.
      2. root1.left와 root2.right가 같고, root1.right와 root2.left가 같음.
  • 두 경우 중 하나라도 만족하면 두 트리는 플립 동등하다고 할 수 있습니다.
• 기저 사례:
  • **두 노드가 모두 None**일 때: 두 트리는 동등함.
  • **하나의 노드만 None**일 때: 두 트리는 다름.
  • 노드 값이 다를 때: 두 트리는 다름.

- 문제풀이

 

• root1 = [1, 2, 3, 4, 5, 6, null, null, null, 7, 8]
• root2 = [1, 3, 2, null, 6, 4, 5, null, null, null, null, 8, 7]

이 문제에서는 두 개의 트리가 "플립 동등성(Flip Equivalent)"을 만족하는지 확인해야 합니다. 플립 동등성이란, 두 트리가 서로 같거나 각 노드에서 왼쪽 자식과 오른쪽 자식을 교환하여 서로 같아질 수 있는 것을 의미합니다.

 

 

플립 동등성이 성립하는지 확인하기 위해 각 노드를 하나씩 비교하면서 왼쪽과 오른쪽 자식을 뒤집는 경우도 고려해야 합니다.

1. 루트 노드 비교:
   • root1과 root2의 루트 값은 둘 다 1입니다. 즉, 루트는 동일합니다.
2. 첫 번째 레벨 비교:
   • root1의 왼쪽 자식은 2이고, 오른쪽 자식은 3입니다.
   • root2의 왼쪽 자식은 3이고, 오른쪽 자식은 2입니다.
   • 두 트리는 자식들이 뒤바뀌어 있지만, 플립 동등성을 만족하므로 다음 레벨로 넘어갑니다.
3. 두 번째 레벨 비교:
   • root1에서 2 노드를 살펴보면:
     • root1의 2 노드의 왼쪽 자식은 4, 오른쪽 자식은 5입니다.
   • root2의 2 노드를 살펴보면:
     • root2의 2 노드의 왼쪽 자식은 4, 오른쪽 자식은 5입니다.
   • 이들은 동일한 구조를 가지므로 그대로 넘어갑니다.
   • root1의 3 노드의 왼쪽 자식은 6입니다.
   • root2의 3 노드의 오른쪽 자식은 6입니다.
   • 자식 위치가 바뀌었지만 값이 동일하므로 플립 동등성이 성립됩니다.
4. 세 번째 레벨 비교:
   • root1의 5 노드의 왼쪽 자식은 7, 오른쪽 자식은 8입니다.
   • root2의 5 노드의 왼쪽 자식은 8, 오른쪽 자식은 7입니다.
   • 자식 위치가 서로 바뀌었지만, 값은 동일합니다. 따라서 이 부분에서도 플립 동등성이 성립합니다.

결론

두 트리는 자식 노드의 위치가 여러 곳에서 서로 바뀌었지만, 각 노드에서 왼쪽과 오른쪽 자식이 바뀌어도 동일한 값을 가지는 경우 플립 동등성을 만족할 수 있습니다.

즉, 각 노드에서 자식이 뒤바뀌어 있더라도 자식들의 값이 같다면 플립 동등 트리로 간주됩니다. 이 예제에서는 모든 노드에서 자식들이 뒤바뀐 경우에도 값이 동일하므로, 두 트리는 플립 동등 트리입니다.

 

 

> java

 

 

class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null || root2 == null || root1.val != root2.val ) {
            return false;
        }
        return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) || 
                (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
    }
}

 

> python

 

class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if root1 is None and root2 is None : return True
        if root1 is None or root2 is None or root1.val != root2.val : return False

        firstFlip = self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)
        secondFlip = self.flipEquiv(root1.right, root2.left) and self.flipEquiv(root1.left, root2.right)

        return firstFlip or secondFlip