翻转等价二叉树
难度:
标签:
题目描述
我们可以为二叉树 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]范围内的整数
代码结果
运行时间: 20 ms, 内存: 16.0 MB
/*
* 思路：
* 使用Java Stream API不能直接解决这个问题，因为它需要对二叉树进行递归遍历。
* 但是我们可以使用递归的方法来实现相同的逻辑。
*/
import java.util.Objects;
public class Solution {
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
return Objects.equals(root1, root2) ||
(root1 != null && root2 != null && root1.val == root2.val &&
((flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||
(flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left))));
}
}
// 定义TreeNode类
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}解释
方法:
本题解采用递归的方式来判断两棵二叉树是否是翻转等价的。首先，如果两个根节点都为空，则它们显然是翻转等价的。如果只有一个节点为空或者两个节点的值不相等，则它们不是翻转等价的。接下来，递归地检查两种情况：一种是两棵树的左子树和右子树分别翻转等价；另一种是一棵树的左子树与另一棵树的右子树翻转等价，同时一棵树的右子树与另一棵树的左子树翻转等价。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在递归函数中，如果根节点的值不相等直接返回false，这种处理是否意味着所有子树的值也必须完全一致才能认为两棵树翻转等价？
▷🦆
递归解法中，如何确保不会因为重复的递归调用导致效率问题？是否有可能存在对同一对节点的多次递归调用？
▷🦆
在递归比较过程中，是否考虑了所有节点的子节点都为空的情况，这种情况下如何处理？
▷🦆
递归解法中，当检查`root1.left`与`root2.right`的翻转等价性时，是否需要考虑它们各自的子树结构可能导致的复杂性增加？
▷