编写一个函数 mirror_tree(root),它接收一个二叉树的根节点 root,并将其转换为原始二叉树的镜像,代码是什么
时间: 2023-08-31 19:38:52 浏览: 92
### 回答1:
请看如下代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def mirror_tree(root: TreeNode) -> TreeNode:
if not root:
return root
root.left, root.right = mirror_tree(root.right), mirror_tree(root.left)
return root
```
在 mirror_tree 函数中,我们首先判断根节点是否为空。如果为空,我们直接返回根节点。
接下来,我们交换根节点的左右子树,并分别递归处理左右子树。最后返回根节点。这样就完成了二叉树的镜像转换。
### 回答2:
如下所示是编写一个函数 `mirror_tree(root)` 的代码,它能够将给定二叉树的根节点 `root` 转换为原始二叉树的镜像:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def mirror_tree(root):
if root is None: # 若根节点为空,则直接返回
return None
root.left, root.right = mirror_tree(root.right), mirror_tree(root.left) # 交换左右子树
return root
# 测试代码
# 创建示例二叉树
# 1
# / \
# 2 3
# / \
# 4 5
# 转换后的镜像二叉树为:
# 1
# / \
# 3 2
# \
# 5
# /
# 4
# 可以使用中序遍历验证镜像二叉树是否正确
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val, end=" ")
inorder_traversal(root.right)
if __name__ == "__main__":
# 创建示例二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 转换为镜像二叉树
mirror_root = mirror_tree(root)
# 验证镜像二叉树是否正确
inorder_traversal(mirror_root)
```
这段代码中使用了二叉树的递归思想,通过交换每个节点的左右子树来实现镜像的转换。当根节点不为空时,首先利用递归函数 `mirror_tree()` 将当前节点的左子树和右子树进行镜像转换,然后将其交换。最后返回根节点即可。
### 回答3:
函数 mirror_tree(root) 的关键是将二叉树的左右子树进行交换。具体的解决思路如下:
首先,判断根节点 root 是否为空,若为空则直接返回。
若不为空,则将根节点的左右子树交换。
然后,递归地对根节点的左子树和右子树进行镜像转换,即调用 mirror_tree(root.left) 和 mirror_tree(root.right)。
最后,返回根节点。
以下是相应的代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def mirror_tree(root):
if not root: # 根节点为空,直接返回
return
# 交换根节点的左右子树
root.left, root.right = root.right, root.left
# 递归地对左右子树进行镜像转换
mirror_tree(root.left)
mirror_tree(root.right)
return root
```
示例:
假设二叉树如下所示:
```
1
/ \
2 3
/ \
4 5
```
调用 mirror_tree(root),返回的镜像二叉树如下所示:
```
1
/ \
3 2
/ \
5 4
```
经过镜像转换后,原始二叉树的左右子树互换了位置。
阅读全文