题目描述

扭转后等价的二叉树

给定两棵二叉树，我们需要判断它们是否通过一次旋转操作变得等价。这里所说的“旋转操作”指的是将一棵树的左子树变为右子树，或者将右子树变为左子树，而树中的节点值及节点之间的连接关系不发生变化。

两棵树被认为是等价的，如果它们可以通过一系列的旋转操作相互转换得到。

示例：

    1            1
   / \          / \
  2   3    ->   3   2
 /                 \
4                   4

在上面的示例中，第一棵树通过一次旋转操作可以变成第二棵树，因此它们是等价的。

PHP 示例代码

以下是一个使用 PHP 编写的函数来判断两棵二叉树是否等价（通过旋转）：

class TreeNode {
    public $val;
    public $left;
    public $right;
    
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function isFlipEquiv(TreeNode $root1, TreeNode $root2) {
    // 基本情况判断
    if ($root1 == null && $root2 == null) return true;
    if ($root1 == null || $root2 == null) return false;
    if ($root1->val != $root2->val) return false;

    // 检查四种可能的旋转等价情况
    return (isFlipEquiv($root1->left, $root2->left) && isFlipEquiv($root1->right, $root2->right)) ||
           (isFlipEquiv($root1->left, $root2->right) && isFlipEquiv($root1->right, $root2->left));
}

// 示例用法
$root1 = new TreeNode(1);
$root1->left = new TreeNode(2);
$root1->right = new TreeNode(3);
$root1->left->left = new TreeNode(4);

$root2 = new TreeNode(1);
$root2->left = new TreeNode(3);
$root2->right = new TreeNode(2);
$root2->right->right = new TreeNode(4);

echo isFlipEquiv($root1, $root2) ? "Trees are flip equivalent" : "Trees are not flip equivalent";

Python 示例代码

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isFlipEquiv(root1, root2):
    if not root1 and not root2:
        return True
    if not root1 or not root2:
        return False
    if root1.val != root2.val:
        return False
    return (isFlipEquiv(root1.left, root2.left) and isFlipEquiv(root1.right, root2.right)) or \
           (isFlipEquiv(root1.left, root2.right) and isFlipEquiv(root1.right, root2.left))

# 示例用法
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
root1.left.left = TreeNode(4)

root2 = TreeNode(1)
root2.left = TreeNode(3)
root2.right = TreeNode(2)
root2.right.right = TreeNode(4)

print("Trees are flip equivalent" if isFlipEquiv(root1, root2) else "Trees are not flip equivalent")

JavaScript 示例代码

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function isFlipEquiv(root1, root2) {
    if (!root1 && !root2) return true;
    if (!root1 || !root2) return false;
    if (root1.val !== root2.val) return false;
    return (isFlipEquiv(root1.left, root2.left) && isFlipEquiv(root1.right, root2.right)) ||
           (isFlipEquiv(root1.left, root2.right) && isFlipEquiv(root1.right, root2.left));
}

// 示例用法
let root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);
root1.left.left = new TreeNode(4);

let root2 = new TreeNode(1);
root2.left = new TreeNode(3);
root2.right = new TreeNode(2);
root2.right.right = new TreeNode(4);

console.log(isFlipEquiv(root1, root2) ? "Trees are flip equivalent" : "Trees are not flip equivalent");

码小课网站中有更多关于二叉树、递归和算法设计的相关内容分享给大家学习，欢迎访问。