当前位置： 面试刷题>> 扭转后等价的二叉树 (经典算法题500道)
### 题目描述
**扭转后等价的二叉树**
给定两棵二叉树，我们需要判断它们是否通过一次旋转操作变得等价。这里所说的“旋转操作”指的是将一棵树的左子树变为右子树，或者将右子树变为左子树，而树中的节点值及节点之间的连接关系不发生变化。
两棵树被认为是等价的，如果它们可以通过一系列的旋转操作相互转换得到。
**示例**：
```
1 1
/ \ / \
2 3 -> 3 2
/ \
4 4
```
在上面的示例中，第一棵树通过一次旋转操作可以变成第二棵树，因此它们是等价的。
### PHP 示例代码
以下是一个使用 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 示例代码
```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 示例代码
```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");
```
**码小课**网站中有更多关于二叉树、递归和算法设计的相关内容分享给大家学习，欢迎访问。