给定一棵用二叉链表表示的二叉树,其根指针为 root,试写出将二叉树中所有结的左、右子树相互交换的算法。
时间: 2023-06-12 10:01:56 浏览: 55
好的,我可以为您提供这个算法,以下是代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(root: TreeNode) -> TreeNode:
if not root:
return None
# 递归左右子树
left = invertTree(root.left)
right = invertTree(root.right)
# 交换左右子树
root.left = right
root.right = left
return root
```
这个算法使用了递归的思想,可以将二叉树中所有节点的左右子树相互交换。您可以将该代码添加到您的项目中,并使用它交换二叉树中所有节点的左右子树。希望以上信息能够帮助到您!
相关问题
给定一棵用二叉链表表示的二叉树,其根指针为 root,试写出将二叉树中所有结的左、右子树相互交换的算法
好的,让我来回答您的问题。
这里给出将二叉树中所有节点的左、右子树相互交换的算法:
```
void swapTree(TreeNode *root) {
if (root == nullptr) {
return;
}
swap(root->left, root->right);
swapTree(root->left);
swapTree(root->right);
}
```
这个算法使用递归方式实现,从根节点开始遍历树,对每个节点的左、右子树进行交换,并分别递归地对交换后的左、右子树进行处理,直到所有节点都被处理。
希望能够满足您的需求,如果还有其他问题,请继续提问。
给定一棵用二叉链表表示的二叉树,其根指针为 root,试写出求二叉树结点的数的算法。
当您输入 "给定一棵用二叉链表表示的二叉树,其根指针为 root,试写出求二叉树结点的数的算法。" 时,我的ChitGPT AI将给予以下回答:
可以使用递归的方式来求解二叉树结点的数。具体地,对于一棵二叉树,其结点数等于其左子树的结点数加上右子树的结点数再加上1(根结点)。
因此,可以定义一个递归函数countNodes,以某个结点为根的子树作为参数,返回该子树中的结点数。具体实现方式如下:
int countNodes(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
其中,当给出的子树为空时,其结点数为0;否则,使用递归计算其左子树和右子树的结点数,并相加1(根结点数),即可得到该子树的结点数。
希望以上回答能够帮助您。