交换二叉树每个结点的左孩子和右孩子算法思路,文字描述+代码(如果只有一个孩子的情况也要考虑)
时间: 2023-11-15 20:05:20 浏览: 29
交换二叉树每个结点的左孩子和右孩子的算法实现可以通过递归来完成。对于每个节点,将它的左孩子和右孩子交换,然后再递归的交换左右子树。需要注意的是,如果节点没有左子树或者右子树,就不需要进行交换。
以下是交换二叉树每个结点的左孩子和右孩子的算法实现的Python代码:
```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 root is None:
return None
# 交换左右子树
root.left, root.right = root.right, root.left
# 递归交换左右子树
invertTree(root.left)
invertTree(root.right)
return root
```
对于一个二叉树的节点,我们首先交换它的左右孩子,然后再递归地交换左孩子和右孩子。最后,返回交换后的根节点即可。
相关问题
交换二叉树每个结点的左孩子和右孩子算法思路,文字描述+代码
交换二叉树每个结点的左孩子和右孩子的算法思路如下:
1. 如果当前节点为空,返回。
2. 如果当前节点有左孩子和右孩子,交换它们。
3. 递归交换当前节点的左孩子和右孩子。
4. 递归交换当前节点的左子树和右子树。
代码实现如下(假设二叉树节点类型为Node):
```
void swapTree(Node* root) {
if (!root) {
return;
}
// 交换当前节点的左孩子和右孩子
Node* temp = root->left;
root->left = root->right;
root->right = temp;
// 递归交换左右孩子
swapTree(root->left);
swapTree(root->right);
}
```
使用方法:
假设有一棵名为root的二叉树,调用swapTree函数即可交换它的左右孩子:
```
swapTree(root);
```
以二叉链表作为二叉树的存储结构,编写交换二叉树每个结点的左孩子和右孩子的算法
交换二叉树每个节点的左孩子和右孩子的算法可以通过递归实现。具体步骤如下:
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 invertTree(root: TreeNode) -> TreeNode:
if not root:
return None
# 交换左右子树
root.left, root.right = root.right, root.left
# 递归左右子树
invertTree(root.left)
invertTree(root.right)
return root
```
在上述代码中,我们定义了一个 `TreeNode` 类来表示二叉树中的每个节点。然后,我们定义了一个名为 `invertTree` 的函数,该函数接受一个二叉树的根节点,并返回交换后的根节点。
在函数中,我们首先检查当前节点是否为空。如果为空,我们直接返回。否则,我们交换当前节点的左右孩子节点,并递归处理当前节点的左子树和右子树。
最后,我们返回交换后的根节点。