交换二叉树中每个节点的左孩子和右孩子代码加解析
时间: 2023-11-13 21:05:04 浏览: 40
可以通过递归的方式交换每个节点的左孩子和右孩子。具体的代码实现如下:
```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
```
在这个代码中,我们首先判断了根节点是否为空。如果为空,则直接返回空。如果不为空,则递归交换左右子树:将当前节点的左子树传入递归函数中进行交换,将当前节点的右子树传入递归函数中进行交换,最后将左右子树交换。最后,返回根节点即可。
这个算法的时间复杂度是 O(n),其中 n 是二叉树的节点数。因为我们需要遍历二叉树的每一个节点并交换它们的左右子树。空间复杂度也是 O(n),因为在最坏情况下,递归调用栈的深度可能会达到 n。
相关问题
交换二叉树中每个节点的左孩子和右孩子的伪代码
以下是交换二叉树中每个节点的左孩子和右孩子的伪代码:
```
SwapLeftAndRight(root):
if root is null:
return
temp = root.left
root.left = root.right
root.right = temp
SwapLeftAndRight(root.left)
SwapLeftAndRight(root.right)
```
其中,`root` 表示二叉树的根节点,`root.left` 表示根节点的左孩子,`root.right` 表示根节点的右孩子。我们首先判断根节点是否为空,如果为空则返回。否则,我们交换根节点的左孩子和右孩子,然后递归交换根节点的左子树和右子树。
交换二叉树中每个节点的左孩子和右孩子
### 回答1:
交换二叉树中每个节点的左孩子和右孩子,可以通过递归实现。具体步骤如下:
1. 如果当前节点为空,直接返回。
2. 交换当前节点的左右孩子。
3. 递归交换当前节点的左子树。
4. 递归交换当前节点的右子树。
代码如下:
```
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);
}
```
其中,TreeNode是二叉树节点的结构体,包含左右孩子指针和节点值等信息。
### 回答2:
交换二叉树中每个节点的左孩子和右孩子,需要遍历这个二叉树,对于每一个节点,将其左孩子和右孩子交换即可。
具体实现可以使用递归方法或迭代方法,以下是递归实现的步骤:
首先定义一个递归函数swap,它需要接受一个二叉树节点作为参数,返回交换之后的二叉树节点。
在函数内部,首先判断当前节点是否为空,如果为空则直接返回空节点。
否则,我们可以通过递归的方式将当前节点的左子树和右子树分别交换,并将交换之后的节点赋值给当前节点的左右孩子。
最后返回当前节点即可。
具体的代码实现如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def swap(root):
if root:
left = swap(root.left)
right = swap(root.right)
root.left = right
root.right = left
return root
```
在以上代码中,我们定义了一个二叉树节点类TreeNode,其中包含了节点的值val和左右孩子left、right。
同时,我们定义了一个swap函数,接受一个二叉树节点作为参数,并返回交换之后的二叉树节点。
通过递归的方式,我们可以实现二叉树的交换,即先递归交换左子树和右子树,再交换当前节点的左右孩子。
最后,我们返回交换之后的根节点即可。
综上所述,交换二叉树中每个节点的左孩子和右孩子,可以通过递归遍历二叉树,并交换每个节点的左右孩子来实现。
### 回答3:
交换二叉树中每个节点的左孩子和右孩子,可以通过递归的方式实现。我们可以从根节点开始,依次将每个子树的左右子节点交换位置,然后再分别对每个子树进行同样的操作。具体的实现步骤如下:
1. 如果根节点为空或者没有子节点,直接返回。
2. 如果根节点有左右子节点,先将左右子节点交换位置。
3. 对根节点的左子树和右子树分别进行同样的操作,即将左右子节点交换位置。
4. 递归结束后,整棵树的左右子节点已经交换位置。
代码实现如下:
```
public void invertTree(TreeNode root) {
if (root == null) {
return;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
}
```
以上代码实现了交换二叉树中每个节点的左孩子和右孩子。该方法的时间复杂度为O(n),其中n为二叉树节点的个数。因为对每个节点都需要进行交换操作,所以时间复杂度为线性。