951. 翻转等价二叉树 - Flip Equivalent Binary Trees

🎯 问题描述（来源于LeetCode）

描述：
给定两棵二叉树的根节点 root1 和 root2，判断它们是否翻转等价。
定义：如果可以通过执行若干次“翻转”操作（交换任意节点的左右子节点）使一棵树变成另一棵树，则两棵树翻转等价。

说明：

“翻转”操作可以应用在任意节点上，次数不限。
空树与自身翻转等价。

示例：

示例 1：

1 2	输入: 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

示例 2：

1 2	输入: root1 = [], root2 = [] 输出: true

示例 3：

1 2	输入: root1 = [], root2 = [1] 输出: false

💻 解题思路

思路1：递归 + 分情况讨论（翻转 / 不翻转）

算法步骤

处理空节点：
- 如果 root1 或 root2 有一个为 None，则只有两者同时为 None 时才返回 True，否则 False。
比较根节点值：
- 如果两棵树根节点值不同，直接返回 False（无法通过翻转使值相等）。
递归检查子树（两种可能性）：
- 不翻转：左子树与左子树比较，右子树与右子树比较。
  即 flipEquiv(root1.left, root2.left) and flipEquiv(root1.right, root2.right)
- 翻转：左子树与右子树比较，右子树与左子树比较。
  即 flipEquiv(root1.left, root2.right) and flipEquiv(root1.right, root2.left)
返回结果：
- 只要两种检查中至少有一种成立，则两棵树翻转等价。

思路1：代码实现

# 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 or root2 is None:
            return root1 == root2
        flip = root1.val == root2.val and self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left)
        no_flip = root1.val == root2.val and self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)
        return flip or no_flip

思路1：📊 性能分析

复杂度验证

时间复杂度： $O(\min(n, m))$ ，最坏情况下（两棵树相同或翻转等价时）每个节点被访问一次。实际递归会探索两条路径，但由于剪枝（值不等时立即返回 False），整体复杂度为 $O(n)$ ， $n$ 为节点数较少的树的节点数。
空间复杂度： $O(h)$ ，其中 $h$ 为树的高度。递归调用栈的深度最大为树高，最坏情况（链状）为 $O(n)$ 。

思考

本题的核心在于灵活处理翻转：不需要真正翻转树，只需在递归时交叉比较子树即可。

注意代码中 flip 和 no_flip 都先判断 root1.val == root2.val，实际上可以提前判断，避免重复比较。简洁写法可以写成：

1
2
3

return (root1.val == root2.val and
        ((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))))