LeetCode 951. Flip Equivalent Binary Trees
링크
제약조건
- The number of nodes in each tree is in the range [0, 100].
- Each tree will have unique node values in the range [0, 99].
풀이방법
재귀를 이용해서 풀 수 있다. 내가 놓쳤던 부분이 두개의 노드가 대칭인 경우도 Flip Equivalent Binary Tree로 간주되는 부분이었다. (문제를 더 꼼꼼히 읽었어야 했다)
코드
# 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 not root1 and not root2:
return True
if not root1 or not root2 or root1.val != root2.val:
return False
return self.flipEquiv(root1.right, root2.left) and self.flipEquiv(root1.left, root2.right) or self.flipEquiv(root1.right, root2.right) and self.flipEquiv(root1.left, root2.left)m
시간복잡도
O(min(N1,N2))
공간복잡도
O(min(H1,H2))