解题思路

使用递归 $DFS$ 判断两棵树是否翻转等价。

对于当前两个节点 $a$ 和 $b$：

如果 $a$ 和 $b$ 都是 $-1$，说明都是空节点，返回 $true$。

如果只有一个是 $-1$，返回 $false$。

题目描述

我们可以为一棵二叉树 $T$ 定义一个 翻转操作：

选择任意一个节点，交换它的左子树和右子树。

只要经过一定次数的翻转操作后，能够使二叉树 $X$ 等于二叉树 $Y$，我们就称二叉树 $X$ 翻转等价于二叉树 $Y$。

给定两棵二叉树 $root1$ 和 $root2$，请判断它们是否翻转等价。

如果两棵二叉树翻转等价，输出 $true$；否则输出 $false$。

输入描述

输入包含两棵二叉树的信息。

对于每棵二叉树：

第一行输入两个整数 $n$ 和 $root$，分别表示二叉树的节点个数和根节点的值。

如果 $n = 0$，则 $root = -1$，表示这是一棵空树。

接下来输入 $n$ 行，每行输入三个整数 $x$、$left$、$right$，表示节点 $x$ 的左孩子为 $left$，右孩子为 $right$。

如果某个孩子不存在，则用 $-1$ 表示。

两棵二叉树的节点值均唯一。

输出描述

输出一行。

如果两棵二叉树翻转等价，输出 $true$；否则输出 $false$。

样例 $1$

样例输入

8 1
1 2 3
2 4 5
3 6 -1
4 -1 -1
5 7 8
6 -1 -1
7 -1 -1
8 -1 -1
8 1
1 3 2
3 6 -1
2 4 5
6 -1 -1
4 -1 -1
5 8 7
8 -1 -1
7 -1 -1

样例输出

true

样例解释

可以翻转值为 $1$、$3$ 以及 $5$ 的三个节点，使两棵二叉树相等。

样例 $2$

样例输入

0 -1
0 -1

样例输出

true

样例 $3$

样例输入

0 -1
1 1
1 -1 -1

样例输出

false

数据范围

• 每棵树的节点数在 $[0,100]$ 范围内
• 每棵树中的每个节点值都是唯一的
• 每个节点值都是在 $[0,99]$ 范围内的整数