编写一个算法,完成对一棵二叉树的左右子树的交换
时间: 2023-05-11 15:02:15 浏览: 113
可以使用递归的方式来完成二叉树的左右子树交换,具体实现如下:
```
void swapTree(TreeNode* root) {
if (root == nullptr) {
return;
}
swap(root->left, root->right);
swapTree(root->left);
swapTree(root->right);
}
```
其中,swapTree 函数接收一个二叉树的根节点,首先交换根节点的左右子树,然后递归地对左右子树进行交换。在交换左右子树时,可以使用 std::swap 函数来完成。
相关问题
3.编写将一棵二叉树的所有左右子树进行交换的算法。
可以使用递归的方法实现二叉树的左右子树交换。具体实现步骤如下:
1. 如果二叉树为空,直接返回空。
2. 如果二叉树不为空,交换当前节点的左右子树。
3. 递归交换当前节点的左子树和右子树。
4. 返回当前节点。
以下是该算法的 Python 代码实现:
```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
```
该算法的时间复杂度是O(n),其中n是二叉树的节点数,因为每个节点都需要被访问一次。空间复杂度是O(h),其中h是二叉树的高度,因为递归调用的栈空间最大深度为树的高度。
编写算法交换二叉树的左右子树
可以使用递归的方式,对于每个节点,交换其左右子树即可。具体实现如下:
```
void invertBinaryTree(TreeNode* root) {
if (root == nullptr) {
return;
}
swap(root->left, root->right);
invertBinaryTree(root->left);
invertBinaryTree(root->right);
}
```
其中 `TreeNode` 是二叉树节点的定义,包括左右子节点指针。可以将这个函数作为类的静态成员方法,方便调用。