编写递归算法,将二叉树中所有结点的左右子树相互交换。
时间: 2023-06-16 10:07:04 浏览: 86
用递归算法把所有结点的左右子树互相交换
递归地交换二叉树节点的左右子树,可以使用下面的算法:
1. 如果二叉树为空,返回 NULL。
2. 如果二叉树非空,则交换左右子树。
3. 递归交换左子树。
4. 递归交换右子树。
5. 返回交换后的根节点。
下面是实现这个算法的递归函数:
```python
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
```
该函数接受一个二叉树的根节点作为参数,并返回交换后的根节点。如果根节点为空,函数返回 None。否则,函数首先交换根节点的左右子树,然后递归地交换左子树和右子树,并返回交换后的根节点。
阅读全文