LeetCode 951. 翻转等价二叉树

约 4 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节 百度
标签
深度优先搜索 树 二叉树

题目描述

✅ 951. 翻转等价二叉树

image-20260928225409186

image-20260928225409187

题意分析

在二叉树的任意节点，可以交换它的左右子树。判断第一棵树能否通过若干次这样的操作，变成与第二棵树节点值和结构都相同的树。各节点可以独立选择是否翻转，也允许一次都不翻转。

操作不会改变某棵子树的根值，也不会把后代移到另一层，只改变左右方向。题目保证每棵树内部的节点值互不相同；本题只返回是否等价，不需要实际修改树或输出翻转步骤。

解法：递归比较两种子树配对

核心思路

[!blue]

定义 flipEquiv(a, b) 表示以这两个节点为根的子树是否翻转等价。两者都为空时已经相同，返回真；只有一个为空时结构无法对应，返回假；两者都存在但根值不同时，交换孩子也无法改变根值，同样返回假。

根值相同后，当前层只有两种可能的孩子对应关系。不翻转当前根时，第一棵树的左子树必须对应第二棵树的左子树，右子树也必须对应右子树；翻转当前根时，左子树对应右子树，右子树对应左子树。

同一种对应关系中的两对子树必须同时等价，所以使用逻辑与；两种对应关系只要任意一种成立，当前两棵子树就等价，所以外层使用逻辑或。递归继续允许子树内部自行翻转，而不是要求整棵树统一采用同一个方向。

这两种对应覆盖了当前节点的全部选择，因此不会漏解；一旦某种对应的两侧都成立，把各子树的翻转方案与当前选择组合起来，又确实能使整棵子树一致，所以也不会误判。

代码先尝试同向对应，成功就直接返回，否则再尝试交叉对应。利用根值比较尽早排除不可能的配对，全程只读取节点，不交换原树的孩子指针。

解题步骤

  1. 两个节点都为空时返回真；仅一个为空或根值不同则返回假。
  2. 递归检查左对左、右对右是否同时成立，若成立直接返回真。
  3. 否则检查左对右、右对左是否同时成立，并返回这个结果。

代码实现

class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }

        if (root1 == null || root2 == null || root1.val != root2.val) {
            return false;
        }

        // 同向对应时，左右两对子树必须都匹配。
        boolean sameOrder =
                flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);

        if (sameOrder) {
            return true;
        }

        // 交换对应仍需同时匹配两对子树。
        return flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);
    }
}

func flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {
    if root1 == nil && root2 == nil {
        return true
    }
    if root1 == nil || root2 == nil || root1.Val != root2.Val {
        return false
    }

    // 同向对应时，左右两对子树必须都匹配。
    sameOrder := flipEquiv(root1.Left, root2.Left) && flipEquiv(root1.Right, root2.Right)
    if sameOrder {
        return true
    }

    // 交换对应仍需同时匹配两对子树。
    return flipEquiv(root1.Left, root2.Right) && flipEquiv(root1.Right, root2.Left)
}

复杂度分析

  • 时间复杂度：$O(n_1 + n_2)$ 上界，其中 n_1、n_2 为两树节点数。题目保证每棵树的值互异，某个非空节点只能与另一棵树中唯一同值节点继续深入，其余尝试在根值处立即结束。
  • 空间复杂度：$O(h)$，h 为两棵树高度的较大值，递归调用沿节点向下的路径展开，不创建新树。

关键点总结

[!green]

  • 翻转只影响孩子方向，根值相等是非空子树能够等价的必要条件。
  • 同一配对方案的左右两侧取与，不同配对方案之间取或。
  • 每层独立选择方向，不能把判断简化为只比较原树或整棵镜像两种情况。

易错点总结

[!yellow]

  • 只比较节点值集合，忽略了父子层级和分支结构，不能判断是否能通过交换达到一致。
  • 将同一方案的左右条件也写成或，会在只匹配一侧时就误判成功。
  • 只检查同向配对，遗漏本题允许的左右交换；只检查交叉配对则遗漏不需要交换的节点。
  • 判空之前访问根值或孩子，在两树结构不同或为空时会访问空节点。

相似题目

题目 难度 关联与区别
100. 相同的树 简单 本题在同方向匹配失败时还可交叉匹配两个孩子，原题只判断不翻转时是否完全相同。
226. 翻转二叉树 简单 原题交换所有节点的左右孩子，本题可在不同节点独立决定是否交换。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/63927254
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！