951.翻转等价二叉树

翻转等价二叉树

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

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

给你两棵二叉树 root1 和 root2。如果两棵树翻转等价则返回 true，否则返回 false。

示例 1:

输入：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

提示:

• 两棵树中的节点数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

解析

递归比较两个树的节点，对于每个节点，比较四种情况：两个子树相等、不翻转相等、翻转后相等。

var flipEquiv = function (root1, root2) {
  if (!root1 && !root2) return true;
  if (!root1 || !root2 || root1.val !== root2.val) return false;

  return (
    (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||
    (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left))
  );
};

时间复杂度 O(min(n, m))，空间复杂度 O(h)。