0951. Flip Equivalent Binary Trees¶
题目信息¶
- 题号:
0951
- 难度:
Medium
- 主题:
二叉树、子树交换、结构等价
- 原题:
- 重点:
可以在任意数量的节点上交换左、右子树;需要判断一棵树能否通过这些独立翻转变成另一棵树,空树也参与比较
题目重述¶
对二叉树中的任意节点执行一次翻转,会交换该节点的左子树和右子树。可以选择任意节点执行任意次翻转,也可以不执行翻转。
给定两棵二叉树的根节点 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
解释:两棵空树已经具有相同结构,不需要执行任何翻转。