给你一棵二叉树的根节点 root,翻转这棵二叉树,并返回其根节点。
时间: 2024-09-19 14:13:47 浏览: 53
C语言翻转二叉树.zip
好的,以下是翻转二叉树的 Python 代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invert_tree(root):
if not root:
return None
# 交换左右子树
root.left, root.right = root.right, root.left
# 递归翻转左右子树
invert_tree(root.left)
invert_tree(root.right)
return root
```
这段代码首先定义了一个二叉树节点的类 `TreeNode`,包含节点的值 `val`、左子节点 `left` 和右子节点 `right`。然后定义了一个函数 `invert_tree`,接受一个二叉树的根节点 `root` 作为参数,返回翻转后的二叉树的根节点。
在函数中,首先判断根节点是否为空,如果为空则直接返回 `None`。否则,交换根节点的左右子树,即 `root.left` 和 `root.right` 的位置。然后递归地翻转左右子树,即调用 `invert_tree(root.left)` 和 `invert_tree(root.right)`。最后返回翻转后的根节点 `root`。
需要注意的是,这里的二叉树是一个非平衡的二叉树,如果要翻转的是平衡的二叉树(例如每个节点的左子树深度等于右子树深度),那么可以直接对原二叉树进行中序遍历即可翻转整个二叉树。但是这个算法通常在二叉树可能不平衡的情况下使用,因为平衡的二叉树在遍历时可能存在一些特殊情况,需要额外的处理。
阅读全文