发表于 2024.05.28

• 典型的树上递归问题，根据题目描述，只需要判断两棵树的根节点是否相同，然后递归判断左子树和右子树是否相同即可。在比较子树的等价时，需要考虑两种情况：1. 左子树和右子树的根节点相同；2. 左子树和右子树的根节点不同。对于第二种情况，需要交换左右子树的比较顺序。

  class Solution:
      def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
          if root1 is None and root2 is None:
              # 双空, 符合条件
              return True
          elif root1 is None or root2 is None:
              # 单空, 不符合条件
              return False
          if root1.val != root2.val:
              return False
  
          return (
                  self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right) or
                  self.flipEquiv(root1.right, root2.left) and self.flipEquiv(root1.left, root2.right)
          )

• LC 题目链接