flip-equivalent-binary-trees

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.

A binary tree X&nbsp;is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.

Given the roots of two binary trees <code>root1</code> and <code>root2</code>, return <code>true</code> if the two trees are flip equivalent or <code>false</code> otherwise.

&nbsp;
Example 1:
<img alt="Flipped Trees Diagram" src="https://assets.leetcode.com/uploads/2018/11/29/tree_ex.png" style="width: 500px; height: 220px;" />
<pre>
Input: 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]
Output: true
Explanation: We flipped at nodes with values 1, 3, and 5.
</pre>

Example 2:

<pre>
Input: root1 = [], root2 = []
Output: true
</pre>

Example 3:

<pre>
Input: root1 = [], root2 = [1]
Output: false
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in each tree is in the range <code>[0, 100]</code>.</li>
	<li>Each tree will have unique node values in the range <code>[0, 99]</code>.</li>
</ul>

flipEquiv

Flip Equivalent Binary Trees

Tree

Depth-First Search

Binary Tree

我们可以为二叉树 T 定义一个&nbsp;翻转操作&nbsp;，如下所示：选择任意节点，然后交换它的左子树和右子树。

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

这些树由根节点&nbsp;<code>root1</code> 和 <code>root2</code>&nbsp;给出。如果两个二叉树是否是翻转 等价&nbsp;的函数，则返回 <code>true</code> ，否则返回 <code>false</code> 。

&nbsp;

示例 1：

<img alt="Flipped Trees Diagram" src="https://assets.leetcode.com/uploads/2018/11/29/tree_ex.png" />

<pre>
输入：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 的三个节点。
</pre>

示例&nbsp;2:

<pre>
输入: root1 = [], root2 = []
输出: true
</pre>

示例 3:

<pre>
输入: root1 = [], root2 = [1]
输出: false
</pre>

&nbsp;

提示：

<ul>
	<li>每棵树节点数在&nbsp;<code>[0, 100]</code> 范围内</li>
	<li>每棵树中的每个值都是唯一的、在 <code>[0, 99]</code>&nbsp;范围内的整数</li>
</ul>