当前位置： 面试刷题>> 翻转二叉树(经典算法150题)
### 题目描述
给定一棵二叉树的根节点 `root`，请你翻转这棵二叉树，使得每个节点的左右子树互换。翻转后的二叉树应该满足如下条件：
- 翻转后的二叉树的左子树是原二叉树的右子树。
- 翻转后的二叉树的右子树是原二叉树的左子树。
- 翻转后的二叉树中，每个节点的左右子节点也需要继续翻转。
### 示例
假设给定的二叉树如下所示：
```
4
/ \
2 7
/ \ / \
1 3 6 9
```
翻转后的二叉树应该为：
```
4
/ \
7 2
/ \ / \
9 6 3 1
```
### 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 invertTree($root) {
if ($root == null) {
return null;
}
// 递归翻转左右子树
$temp = $root->left;
$root->left = invertTree($root->right);
$root->right = invertTree($temp);
return $root;
}
// 示例用法
$root = new TreeNode(4);
$root->left = new TreeNode(2);
$root->right = new TreeNode(7);
$root->left->left = new TreeNode(1);
$root->left->right = new TreeNode(3);
$root->right->left = new TreeNode(6);
$root->right->right = new TreeNode(9);
$invertedRoot = invertTree($root);
// 输出翻转后的二叉树结构（此处省略打印函数实现）
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(root):
if root is None:
return None
# 递归翻转左右子树
root.left, root.right = invertTree(root.right), invertTree(root.left)
return root
# 示例用法
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
inverted_root = invertTree(root)
# 输出翻转后的二叉树结构（此处省略打印函数实现）
```
### 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 invertTree(root) {
if (!root) {
return null;
}
// 递归翻转左右子树
let temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}
// 示例用法
const root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(7);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(9);
const invertedRoot = invertTree(root);
// 输出翻转后的二叉树结构（此处省略打印函数实现）
```
以上代码分别使用 PHP、Python 和 JavaScript 实现了二叉树的翻转算法，并在示例中构建了初始二叉树以展示翻转后的结果。注意，实际输出翻转后的二叉树结构通常需要额外的遍历函数或可视化工具来实现。