0951. Flip Equivalent Binary Trees

题目信息

题号:

0951

难度:

Medium

主题:

二叉树、子树交换、结构等价

原题:

LeetCode 0951

重点:

可以在任意数量的节点上交换左、右子树;需要判断一棵树能否通过这些独立翻转变成另一棵树,空树也参与比较

题目重述

对二叉树中的任意节点执行一次翻转,会交换该节点的左子树和右子树。可以选择任意节点执行任意次翻转,也可以不执行翻转。

给定两棵二叉树的根节点 root1 和 root2,判断它们是否翻转等价,即能否通过上述操作使两棵树的节点值和父子结构完全相同。若可以返回 true,否则返回 false。

两棵树的节点总数均不超过 100,节点值在 [0, 99] 范围内且每棵树内互不相同。

自建示例

在根节点和内部节点分别翻转:

输入:root1 = [1,2,3,4,5], root2 = [1,3,2,null,null,5,4]
输出:true
解释:翻转 root1 的根节点后,节点 2 移到右侧;再翻转节点 2,其孩子 4、5 的顺序与 root2 一致。

两棵树都为空:

输入:root1 = [], root2 = []
输出:true
解释:两棵空树已经具有相同结构,不需要执行任何翻转。