用Python代码实现设计在链式存储结构上交换二叉树中所有结点左、右子 树的算法
时间: 2024-03-01 21:54:53 浏览: 22
实现交换二叉树中所有节点的左右子树,可以采用递归算法实现,代码如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def exchange_tree(root: TreeNode) -> TreeNode:
if not root:
return None
# 交换左右子树
root.left, root.right = root.right, root.left
# 递归交换左右子树
exchange_tree(root.left)
exchange_tree(root.right)
return root
```
其中,TreeNode是二叉树节点的定义,exchange_tree函数实现了交换二叉树中所有节点的左右子树。在函数中,我们首先判断当前节点是否为空,如果为空则直接返回。接着交换当前节点的左右子树,然后递归交换当前节点的左右子树。最后返回根节点即可。
相关问题
设二叉树采用二叉链表存储,设计递归算法实现二叉树中所有结点的左右孩子交换。
算法思路:
1. 如果二叉树为空,直接返回;
2. 如果二叉树不为空,交换当前节点的左右孩子;
3. 递归交换当前节点的左子树和右子树。
代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def swapChildren(root):
if not root:
return
root.left, root.right = root.right, root.left
swapChildren(root.left)
swapChildren(root.right)
```
测试样例:
```python
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
swapChildren(root)
# 遍历交换后的二叉树
def preorder(root):
if not root:
return
print(root.val, end=' ')
preorder(root.left)
preorder(root.right)
preorder(root) # 1 3 2 7 6 5 4
```
以二叉链表作为二叉树的存储结构,编写算法实现交换二叉树每个结点的左孩子和右孩子。
以下是交换二叉树左右孩子的算法实现:
```python
class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def swap_left_right(root):
if not root:
return
# 递归处理左子树和右子树
swap_left_right(root.left)
swap_left_right(root.right)
# 交换左右子树
root.left, root.right = root.right, root.left
```
使用二叉链表存储二叉树,每个节点包含三个属性:节点值 `val`、左孩子节点 `left`、右孩子节点 `right`。算法通过递归遍历二叉树的每个节点,交换其左右孩子节点,从而实现交换整棵二叉树的左右孩子节点。