JZX轻语：简

LeetCode 951 - 翻转等价二叉树

发表于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

题目链接：https://leetcode.cn/problems/flip-equivalent-binary-trees