Leetcode 951. Flip Equivalent Binary Trees

문제

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에 대해 뒤집는 연산은 곧 왼쪽 서브트리와 오른쪽 서브트리를 교체하는것이다.
• 이진트리 X와 이진트리 Y가 뒤집힘-동치 일 경우, X에서 몇번 뒤집는 연산을 통해 Y 트리를 만들수 있다는 뜻이다.
• 두 이진 트리가 주어질때, 이 둘이 뒤집힘-동치 인지 확인하시오.

예시

1, 3, 5 번 노드에 각각 뒤집기를 실행해 같게 만들수 있다.

제한

• 트리의 노드 갯수는 [0, 100] 범위
• 트리의 노드 값은 [0, 99] 중 유니크하게 정해진다.

풀이

• 일단 자기 자신의 값이 같아야 뒤집힘 동치가 일어나든 말던 같을것이다.
• 예시를 보면 왼쪽 트리의 1의 자식은 2, 3 이고 오른쪽 트리의 1의 자식은 3, 2 이다.
• 뒤집힘이 일어나도 같다면, 이 자식들을 값으로 정렬했을때 반드시 생긴 두 배열의 값이 같아야 할것이다.
• 이를 이용한다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
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:
            return False
		# 값이 달라도 안됨
        if root1.val != root2.val:
            return False
		
        # 자식을 나열하고 값으로 정렬, None은 특이 케이스로 -1
        root1childs = [root1.left, root1.right]
        root2childs = [root2.left, root2.right]

        root1childs.sort(key=lambda k: -1 if k is None else k.val)
        root2childs.sort(key=lambda k: -1 if k is None else k.val)

		# 정렬 후 재귀
        left = self.flipEquiv(root1childs[0], root2childs[0])
        right = self.flipEquiv(root1childs[1], root2childs[1])

        return left and right