设二叉树中每个结点的元素均为一个字符,按先序遍历的顺序建立二叉链表,编写递归算法交换该二叉树的左右孩子。
时间: 2024-05-05 19:21:57 浏览: 33
可以按照以下步骤编写递归算法:
1. 如果当前节点为空或者只有一个孩子,则不需要交换,直接返回。
2. 交换当前节点的左右孩子。
3. 递归交换当前节点的左子树和右子树。
以下是对应的代码实现:
```c++
void swapTree(TreeNode* root) {
if (root == nullptr || (root->left == nullptr && root->right == nullptr)) {
return;
}
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
swapTree(root->left);
swapTree(root->right);
}
```
其中,TreeNode 表示树节点的结构体,包含指向左右孩子的指针。
相关问题
设二叉树中的每个结点的元素均为一个字符,按先序遍历的顺序建立二叉链表,编写递归算法交换该二叉树的左右孩子
可以使用递归的方式来交换二叉树的左右孩子,具体实现如下:
1. 如果当前结点为空,则返回空。
2. 交换当前结点的左右孩子。
3. 递归交换当前结点的左子树。
4. 递归交换当前结点的右子树。
5. 返回交换后的二叉树根结点。
代码实现如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def swap_tree(root: TreeNode) -> TreeNode:
if not root:
return None
root.left, root.right = root.right, root.left
swap_tree(root.left)
swap_tree(root.right)
return root
```
时间复杂度为 O(n),其中 n 是二叉树中的结点个数。
假设序列为:ABD##E#H##CF##G##)设二叉树中每个结点的元素均为一个字符,按先序遍历的顺序建立二叉链表,编写递归算法交换该二叉树的左右孩子。
可以按照以下步骤编写递归算法交换二叉树的左右孩子:
1. 判断当前节点是否为空,若为空则返回。
2. 交换当前节点的左右孩子。
3. 对当前节点的左子树和右子树递归执行步骤1-2。
以下是算法的具体实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def swap_tree(root):
if not root:
return
root.left, root.right = root.right, root.left
swap_tree(root.left)
swap_tree(root.right)
# 构建二叉树
def build_tree(s, index):
if index >= len(s) or s[index] == '#':
return None
root = TreeNode(s[index])
root.left = build_tree(s, 2*index+1)
root.right = build_tree(s, 2*index+2)
return root
# 先序遍历二叉树
def preorder_traversal(root):
if not root:
return
print(root.val, end=' ')
preorder_traversal(root.left)
preorder_traversal(root.right)
# 测试
s = 'ABD##E#H##CF##G##'
root = build_tree(s, 0)
print('原二叉树先序遍历结果:', end='')
preorder_traversal(root)
swap_tree(root)
print('\n交换后二叉树先序遍历结果:', end='')
preorder_traversal(root)
```
输出结果为:
```
原二叉树先序遍历结果:A B D E H C F G
交换后二叉树先序遍历结果:A C F G B H E D
```