LeetCode 951. 翻转等价二叉树

Categories:

题目描述
思路分析
1. 解法一：递归判断（推荐）
相似题目

题目描述

✅ 951. 翻转等价二叉树

思路分析

解法一：递归判断（推荐）

核心思路：

两棵树翻转等价当且仅当根值相同，且子树满足同序或交换后相等。

递归判断 left-left & right-right 或 left-right & right-left。

任一满足即可认为等价。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点个数。

空间复杂度：O(h)，其中 h 表示树的高度（递归栈）。

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 same = flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);
        boolean swapped = flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);

        return same || swapped;
    }
}

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
	}

	same := flipEquiv(root1.Left, root2.Left) && flipEquiv(root1.Right, root2.Right)
	swapped := flipEquiv(root1.Left, root2.Right) && flipEquiv(root1.Right, root2.Left)

	return same || swapped
}

相似题目

题目	难度	考察点
100. 相同的树	简单	二叉树
101. 对称二叉树	简单	二叉树
872. 叶子相似的树	简单	二叉树
652. 寻找重复的子树	中等	二叉树
889. 根据前序和后序遍历构造二叉树	中等	二叉树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/63927254