以二叉链表作为二叉树的存储结构,编写算法:交换二叉树每个结点的左孩子和右孩子。
时间: 2023-05-31 14:17:51 浏览: 249
### 回答1:
算法步骤如下:
1. 如果当前结点为空,则返回。
2. 交换当前结点的左孩子和右孩子。
3. 递归交换当前结点的左子树和右子树。
代码实现如下:
void swap(TreeNode* root) {
if (root == nullptr) {
return;
}
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
swap(root->left);
swap(root->right);
}
### 回答2:
二叉链表是指用链式存储结构来表示二叉树,其中每个结点由三部分组成:数据域、左孩子指针和右孩子指针。交换二叉树中每个结点的左孩子和右孩子需要借助递归实现。具体算法如下:
(1)如果二叉树为空,则返回空。
(2)否则,对于当前结点,先交换其左右孩子。
(3)然后对左右孩子分别递归调用交换函数,直到左右孩子为空。
下面是具体的交换算法实现代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invert_tree(root: TreeNode) -> TreeNode:
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为二叉树中结点的个数。
### 回答3:
二叉链表是一种二叉树的存储结构,其中每个结点包含指向其左右孩子的指针,我们可以通过交换这些指针来实现交换二叉树每个结点的左孩子和右孩子。
具体算法如下:
1. 首先判断根节点是否为空,如果为空则直接返回。
2. 对于非空的根节点,我们可以依次递归地交换它的左孩子和右孩子,直到叶子节点。
3. 在每个递归调用中,我们先判断当前节点是否为空,如果为空则返回。
4. 否则,我们交换当前节点的左孩子和右孩子。
5. 然后递归地对当前节点的左孩子和右孩子进行相同的操作。
6. 最终,整棵树的左右孩子就被交换了。
代码如下:
// 二叉树结点
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void swapTree(TreeNode* root) {
if (!root) return; // 如果根节点为空,直接返回
TreeNode* temp = root->left; // 交换左右孩子
root->left = root->right;
root->right = temp;
swapTree(root->left); // 递归交换左右子树
swapTree(root->right);
}
时间复杂度:O(n),其中 n 为二叉树节点数,因为最坏情况下需要遍历整个二叉树。
空间复杂度:O(h),其中 h 为二叉树的高度,因为递归调用会使用额外的栈空间。
阅读全文