05 August 2008
对于二叉树 T，我们可以定义如下翻转操作：选择任意节点，交换左右子子树。
当且仅当我们可以在经过一定次数的翻转操作后使 X 等于 Y 时，二叉树 X 与二叉树 Y 翻转等效。
给定两棵二叉树 root1 和 root2 的根，如果两棵树翻转等价，则返回 true，否则返回 false。
Recursive
1
2
3
4
5
6
7
8
9
10
class Solution {
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) return true;
if (root1 == null || root2 == null) return false;
if (root1.val != root2.val) return false;
return (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left)) || (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right));
}
}
Iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
Queue<TreeNode> queue = new LinkedList<>();
if (root1 == null && root2 == null)
return true;
if (root1 == null || root2 == null)
return false;
queue.add(root1);
queue.add(root2);
while (!queue.isEmpty()) {
TreeNode a = queue.poll();
TreeNode b = queue.poll();
Integer valA = (a != null) ? a.val : null;
Integer valB = (b != null) ? b.val : null;
if (valA != valB) {
return false;
}
Integer valAL = (a == null || a.left == null) ? null : a.left.val;
Integer valAR = (a == null || a.right == null) ? null : a.right.val;
Integer valBL = (b == null || b.left == null) ? null : b.left.val;
Integer valBR = (b == null || b.right == null) ? null : b.right.val;
if (valAL == valBR && valAR == valBL) {
if (valA != null)
queue.add(a.left);
if (valB != null)
queue.add(b.right);
if (valA != null)
queue.add(a.right);
if (valB != null)
queue.add(b.left);
} else {
if (valA != null)
queue.add(a.left);
if (valB != null)
queue.add(b.left);
if (valA != null)
queue.add(a.right);
if (valB != null)
queue.add(b.right);
}
}
return true;
}
}