Medium

题目描述

对于二叉树 T，我们可以定义一个翻转操作：选择任意节点，然后交换它的左右子树。

当我们经过若干次翻转操作后，能使 X 等于 Y 时，我们称二叉树 X 翻转等价于二叉树 Y。

给你两个二叉树的根节点 root1 和 root2，判断这两个树是否翻转等价。

示例 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] 范围内的整数

解题思路

这是一个经典的递归问题。对于两个节点，如果它们翻转等价，需要满足以下条件：

基本思路：

  1. 如果两个节点都为空，返回 true
  2. 如果只有一个节点为空，返回 false
  3. 如果两个节点值不相等，返回 false
  4. 如果值相等，则需要检查子树的翻转等价性

关键洞察： 对于值相等的两个节点，它们翻转等价当且仅当满足以下两种情况之一：

  • 不翻转情况：左子树对左子树翻转等价，且右子树对右子树翻转等价
  • 翻转情况：左子树对右子树翻转等价，且右子树对左子树翻转等价

这样我们就将问题递归分解为子问题。每个节点都有两种选择：保持原样或翻转，我们只需要其中一种选择能使整个树翻转等价即可。

算法步骤：

  1. 处理边界情况（空节点）
  2. 检查当前节点值是否相等
  3. 递归检查两种匹配方式：直接匹配和交叉匹配
  4. 只要有一种方式成功就返回 true

时间复杂度为 O(min(m,n))，其中 m 和 n 分别是两棵树的节点数。

代码实现

class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        // 边界情况：两个都为空
        if (!root1 && !root2) return true;
        
        // 边界情况：只有一个为空，或值不相等
        if (!root1 || !root2 || root1->val != root2->val) return false;
        
        // 递归检查两种情况：不翻转或翻转
        return (flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right)) ||
               (flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left));
    }
};

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))

public class Solution {
    public bool FlipEquiv(TreeNode root1, TreeNode root2) {
        // 边界情况：两个都为空
        if (root1 == null && root2 == null) return true;
        
        // 边界情况：只有一个为空，或值不相等
        if (root1 == null || root2 == null || root1.val != root2.val) return false;
        
        // 递归检查两种情况：不翻转或翻转
        return (FlipEquiv(root1.left, root2.left) && FlipEquiv(root1.right, root2.right)) ||
               (FlipEquiv(root1.left, root2.right) && FlipEquiv(root1.right, root2.left));
    }
}

var flipEquiv = function(root1, root2) {
    // 边界情况：两个都为空
    if (!root1 && !root2) return true;
    
    // 边界情况：只有一个为空，或值不相等
    if (!root1 || !root2 || root1.val !== root2.val) return false;
    
    // 递归检查两种情况：不翻转或翻转
    return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||
           (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(min(m,n))，其中 m 和 n 分别是两棵树的节点数，最坏情况下需要遍历所有对应的节点
空间复杂度O(min(m,n))，递归调用栈的深度取决于树的高度，最坏情况下为树的节点数