DEV Community
·
951. 翻转等价的二叉树
💡
原文英文，约700词，阅读约需3分钟。
📝
内容提要
给定两个二叉树的根节点，判断它们是否可以通过翻转操作变得相等。翻转操作是交换任意节点的左右子树。通过递归深度优先搜索（DFS）检查树的根值和子树是否相同，时间复杂度为O(N)，空间复杂度为O(H)。
🎯
关键要点
- 给定两个二叉树的根节点，判断它们是否可以通过翻转操作变得相等。
- 翻转操作是交换任意节点的左右子树。
- 二叉树X与二叉树Y是翻转等价的，当且仅当通过一些翻转操作可以使X等于Y。
- 使用递归深度优先搜索（DFS）检查树的根值和子树是否相同。
- 时间复杂度为O(N)，空间复杂度为O(H)。
- 基本情况包括：两个节点都为null时相等，只有一个节点为null时不相等，根值不同则不相等。
- 递归情况检查两种可能性：不翻转和翻转子树。
- TreeNode类表示二叉树中的一个节点，包含值、左子节点和右子节点。
- flipEquiv函数处理基本情况和递归情况，确保子树在任一条件下都是翻转等价的。
❓
延伸问答
如何判断两个二叉树是否可以通过翻转操作变得相等？
通过递归深度优先搜索（DFS）检查树的根值和子树是否相同，考虑翻转和不翻转两种情况。
翻转操作具体是指什么？
翻转操作是交换任意节点的左右子树。
翻转等价的二叉树的基本情况有哪些？
基本情况包括：两个节点都为null时相等，只有一个节点为null时不相等，根值不同则不相等。
翻转等价的二叉树的时间复杂度和空间复杂度是多少？
时间复杂度为O(N)，空间复杂度为O(H)。
如何实现翻转等价的判断函数？
可以实现一个flipEquiv函数，处理基本情况和递归情况，检查子树是否翻转等价。
TreeNode类在二叉树中有什么作用？
TreeNode类表示二叉树中的一个节点，包含值、左子节点和右子节点。
➡️
