难度: Medium
我们可以为二叉树 T 定义一个 翻转操作 ，如下所示：选择任意节点，然后交换它的左子树和右子树。
只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转 等价 于二叉树 Y。
这些树由根节点 root1 和 root2 给出。如果两个二叉树是否是翻转 等价 的函数，则返回 true ，否则返回 false 。
示例 1：
输入：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] 输出：true 解释：我们翻转值为 1，3 以及 5 的三个节点。
示例 2:
输入: root1 = [], root2 = [] 输出: true
示例 3:
输入: root1 = [], root2 = [1] 输出: false
提示：
[0, 100] 范围内[0, 99] 范围内的整数运行时间: 20 ms
内存: 16.0 MB
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.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or \
(self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))
本题解采用递归的方式来判断两棵二叉树是否是翻转等价的。首先，如果两个根节点都为空，则它们显然是翻转等价的。如果只有一个节点为空或者两个节点的值不相等，则它们不是翻转等价的。接下来，递归地检查两种情况：一种是两棵树的左子树和右子树分别翻转等价；另一种是一棵树的左子树与另一棵树的右子树翻转等价，同时一棵树的右子树与另一棵树的左子树翻转等价。
时间复杂度: O(n)
空间复杂度: O(n)
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.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or \
(self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))
是的，如果两个根节点的值不相等，直接返回false意味着在这一层递归中，这两个节点不翻转等价，因此它们的任何子树都不需要再进行比较。但这并不意味着所有子树的值必须按相同顺序一致，因为翻转等价允许左右子树在两棵树间交换。只要最终的结构和节点值经可能的翻转后能对应上，这两棵树就是翻转等价的。
在本题的递归解法中，对每一对节点的比较是独立进行的，不存在重复比较同一对节点的情况。每一次递归调用都是针对当前节点的子节点和对应的可能的翻转子节点进行的。因此，每对节点只会被比较一次，不会存在效率问题由于重复递归调用导致的。
如果两个节点的子节点都为空，这在递归函数中自然处理为翻转等价。因为当递归到叶子节点的子节点（即null）时，根据递归函数的设计，两个都为空的节点比较会返回True，表示它们翻转等价。这种基本情况正确处理了所有节点的子节点都为空的情况。
是的，当检查`root1.left`与`root2.right`的翻转等价性时，必须考虑它们各自的子树结构。这增加了问题的复杂性，因为这种情况下，我们不仅需要考虑这两个子树的根节点值相等，而且还要确保它们的左右子树（或交换后的右左子树）也要翻转等价。这是递归解法中处理的核心复杂性之一，但递归方法能自然地通过递归调用来逐层解决这种复杂性。