LeetCode 题解工作台
翻转等价二叉树
我们可以为二叉树 T 定义一个 翻转操作 ，如下所示：选择任意节点，然后交换它的左子树和右子树。 只要经过一定次数的翻转操作后，能使 X 等于 Y ，我们就称二叉树 X 翻转 等价 于二叉树 Y 。 这些树由根节点 root1 和 root2 给出。如果两个二叉树是否是 翻转 等价 的树，则返回 t…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
class Solution: def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
我们可以为二叉树 T 定义一个 翻转操作 ，如下所示：选择任意节点，然后交换它的左子树和右子树。
只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转 等价 于二叉树 Y。
这些树由根节点 root1 和 root2 给出。如果两个二叉树是否是翻转 等价 的树，则返回 true ，否则返回 false 。
示例 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]范围内的整数
解题思路
方法一
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
def dfs(root1, root2):
if root1 == root2 or (root1 is None and root2 is None):
return True
if root1 is None or root2 is None or root1.val != root2.val:
return False
return (dfs(root1.left, root2.left) and dfs(root1.right, root2.right)) or (
dfs(root1.left, root2.right) and dfs(root1.right, root2.left)
)
return dfs(root1, root2)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
The candidate should demonstrate knowledge of tree traversal techniques and recursion.
- question_mark
Candidates should show the ability to track state during the traversal to handle flipped subtrees.
- question_mark
Expect the candidate to handle edge cases efficiently, especially the scenario where one tree is empty and the other is not.
常见陷阱
外企场景- error
Failure to account for flipped subtrees and incorrectly assuming only direct equality between nodes.
- error
Not properly handling edge cases where one tree is empty or the trees have different structures.
- error
Incorrectly managing recursion, leading to excessive stack usage or incorrect comparisons.
进阶变体
外企场景- arrow_right_alt
Handling unbalanced trees with different shapes and depths.
- arrow_right_alt
Optimizing space complexity by using an iterative approach or a non-recursive traversal.
- arrow_right_alt
Modifying the problem to check for flip equivalence with a limited number of allowed flips.