LeetCode 951. 翻转等价二叉树

2025-08-21 HGNULB 约 8 分钟

文章信息 8 个分类 3 个标签

分类

题目描述

✅ 951. 翻转等价二叉树

题意分析

题目给两棵二叉树，允许对任意节点执行任意多次「交换它的左右子树」这个操作，问能否把第一棵变成第二棵，只要回答是或否。

关键是看清这个操作不改变什么：节点值不变，节点的父子从属关系不变，子树的内部构成不变。它唯一改变的是兄弟之间的左右顺序。所以两棵树若要等价，第一棵的根必须对应第二棵的根，值必须相同，接下来第一棵根的两棵子树也只能整体地对应到第二棵根的两棵子树，不可能拆散重组。

约束里有两条重要信号：节点总数不超过 100，规模很小；每棵树内部的节点值互不相同。后者容易被忽略，但它决定了「谁该对应谁」是没有歧义的，也直接影响到复杂度分析。

边界上要留意：两棵树都为空视为等价；一棵空一棵非空必然不等价，这个判断必须在读取节点值之前完成，否则会解引用空指针；两个节点值不同时应当立刻否定，不能再往下递归。

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

核心思路

最朴素的想法是把「翻转」当成一次真实的操作去搜索：对每个节点决定翻还是不翻，共 $2^n$ 种组合，每种组合都把树重排一遍再和目标树逐节点比对。这在思路上是对的，但把所有节点的翻转决策当成需要联合枚举的全局自由变量，代价是指数级的。

瓶颈在于这个「联合」是虚假的。翻转某个节点，影响范围仅限于它的两棵子树谁排在左边，完全不影响子树内部要怎么翻，也不影响树上其它分支。也就是说，各节点的决策彼此独立，可以就地各自定夺，不需要笛卡尔积式地铺开。

顺着这条线索定义谓词：flipEquiv(a, b) 表示「以 a 为根的子树能否经过若干次翻转变成以 b 为根的子树」。这个谓词的取值只依赖 (a, b) 这一对节点，与它们各自在原树中的位置、与祖先节点翻没翻过，统统无关——这正是可以自顶向下拆解的根据，也是整道题的核心不变量。

有了谓词就能写出递推：a 和 b 要等价，首先值必须相同；其次 a 的左右子树必须整体对应到 b 的左右子树，而对应方式只有两种——不翻转时是「a 左配 b 左、a 右配 b 右」，翻转时是「a 左配 b 右、a 右配 b 左」。两种方式只要有一种成立即可，所以取或。至此 $2^n$ 的联合枚举被压成了每个节点上的常数次判断。

最后利用「每棵树内值互不相同」这个条件做一个复杂度上的观察：a 的左孩子的值最多和 b 的左右孩子之一相同，所以两种配对方式中必然至少有一种在第一层值比较处就被直接否掉，只有另一种会真正深入递归。这保证了每一对节点最多被深度展开一次，总时间是线性而非指数。

解题步骤

先处理双空：两个节点同时为空，返回 true。为什么放在最前：空对空是合法的等价情形，且后面所有分支都建立在「至少有一个非空」之上。

再处理单空与值不等：只要有一个为空（另一个非空），或者两者值不同，返回 false。为什么必须合并在这一步：短路求值保证访问 val 之前两个指针都已非空，顺序反了直接空指针崩溃；而值不同时继续递归既无意义，又会丢掉本题最重要的剪枝。

计算不翻转的配对：递归判断 a 的左孩子对 b 的左孩子、且 a 的右孩子对 b 的右孩子。为什么两个子问题之间是「且」：翻不翻是对当前节点的一次决定，一旦定下来，两侧必须同时成立才算这种排法可行。

若不翻转已成立，立刻返回 true。为什么要提前返回：这是短路，能省掉另一种配对的整棵递归。

否则计算翻转的配对：a 的左孩子对 b 的右孩子、且 a 的右孩子对 b 的左孩子，把结果直接返回。为什么两种配对之间是「或」：题目允许翻转但不强制，只要存在一种排法可行，两棵子树就是等价的。

以 root1 = [1,2,3,4,5]、root2 = [1,3,2,null,null,5,4] 走一遍：第一棵树的根是 1，左孩子 2（其左右孩子分别是叶子 4 和叶子 5），右孩子是叶子 3；第二棵树的根也是 1，左孩子是叶子 3，右孩子是 2（其左右孩子分别是叶子 5 和叶子 4）。

调用 flipEquiv(1, 1)：都非空且值都是 1，通过前两道边界。

先算不翻转的配对，第一个子问题是 flipEquiv(2, 3)：两者都非空但值 2 和 3 不同，立刻返回 false。因为是「且」，第二个子问题被短路掉不再计算，不翻转这条路失败。

转而计算翻转的配对，第一个子问题是 flipEquiv(2, 2)（第一棵的左孩子对第二棵的右孩子）：值相同，进入下一层。它的不翻转配对是 flipEquiv(4, 5)，值 4 和 5 不同返回 false；于是尝试翻转配对 flipEquiv(4, 4) 与 flipEquiv(5, 5)。前者两个节点的孩子全为空，不翻转配对的两个子问题都是双空返回 true，于是 flipEquiv(4, 4) 为 true；同理 flipEquiv(5, 5) 也为 true。两者相与，flipEquiv(2, 2) 返回 true。

翻转配对的第二个子问题是 flipEquiv(3, 3)（第一棵的右孩子对第二棵的左孩子）：值相同，两边孩子全为空，不翻转配对直接成立，返回 true。

两个子问题都为 true，flipEquiv(1, 1) 返回 true。对应的实际操作是：先翻转根节点使 3 和 2 互换位置，再翻转节点 2 使 4 和 5 互换位置，第一棵树就变成了第二棵。

代码实现

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)$，虽然每个节点对都尝试两种配对，但题目保证同一棵树内值互不相同，两种配对中至少有一种在第一层值比较处就被 $O(1)$ 否掉，因此每个节点最多被深度展开一次。

空间复杂度：$O(h)$，其中 $h$ 是树高，唯一开销是递归栈；树可能退化成链，最坏情况下 $h = n$。

关键点总结

判定两个结构「在某种变换下是否等价」时，先问这个变换不改变什么。翻转不改变值、不改变父子从属，只改变兄弟顺序，这句话直接框定了对应关系只能是根对根、子树对子树。

把递归函数写成一个只依赖参数对的谓词，并明确它与祖先决策无关，是把指数级联合枚举降为线性的关键；这个「无关性」值得在面试里说出来，而不是默认。

分支之间的逻辑连接符要和题意对齐：同一种排法内部两侧是「且」，不同排法之间是「或」，写反任何一个都会给出系统性的错误答案。

边界判断的书写顺序即是安全顺序，双空、单空、值不等三道关卡必须依次挡在解引用之前。

面试视角：这题看着简单，真正的加分点是复杂度论证。能主动指出「值互不相同保证了两条分支里只有一条会深入」，比写出代码本身更能体现深度。

面试视角：面试官可能追问「如果值允许重复呢」。此时两条分支都可能深入，最坏退化成指数，需要改用子树哈希或按值排序的规范形式来比较，可以主动给出这个方向。

易错点总结

错误写法：只判断 root1 == null 就返回 true，没有同时确认 root2 也为空。用例 root1 = []、root2 = [1] → 返回 true，正确答案是 false。

错误写法：双空判断之后不检查单空，直接读取 root1.val。用例 root1 = [1,2]、root2 = [1] → 递归到「节点 2 对空」这一对时解引用空指针，程序崩溃。

错误写法：值不同时不返回 false 而是继续往下递归。用例 root1 = [1]、root2 = [2] → 两个节点的孩子全为空，配对全部成立，返回 true，正确答案是 false。

错误写法：两种配对之间用「且」而不是「或」。用例 root1 = [1,2,3]、root2 = [1,3,2] → 不翻转的配对失败就直接判负，返回 false，正确答案是 true。

错误写法：同一种配对内部的两侧用「或」而不是「且」。用例 root1 = [1,2,3]、root2 = [1,2,4] → 左侧 2 对 2 成立就认为整体成立，返回 true，但右侧 3 和 4 根本不同，正确答案是 false。

错误写法：不翻转配对的第二个子问题写错方向，比如写成 flipEquiv(root1.right, root2.left)。用例 root1 = [1,2,3]、root2 = [1,2,3] → 不翻转配对因为 3 对 2 失败，翻转配对又是 2 对 3 和 3 对 2 双双失败，返回 false，正确答案是 true。

错误写法：把问题理解成「两棵树的节点值集合相同即可」，改用遍历后排序比较。用例 root1 = [1,2,3,4]（4 是 2 的左孩子）与 root2 = [1,2,3,null,null,4]（4 是 3 的左孩子）→ 值集合都是 ${1,2,3,4}$，被判为 true，但 4 的父亲不同，翻转永远换不过来，正确答案是 false。

错误写法：真的去修改树结构执行翻转再比较。用例任意需要多处翻转的输入 → 破坏了输入数据，且失败分支必须逐一撤销翻转，漏撤一次后续判断全错。

相似题目

题目	难度	考察点
100. 相同的树	简单	只有一种配对方式，是本题去掉翻转自由度后的退化形态
101. 对称二叉树	简单	固定采用交叉配对，判断一棵树与自身镜像是否相同
572. 另一棵树的子树	简单	需要枚举锚点，把相等判定嵌套在一次外层遍历里
226. 翻转二叉树	简单	真正执行左右交换并返回新树，是构造而非判定