用python语言实现交换左右子树

假设我们有一棵二叉树，可以使用以下代码实现交换左右子树：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def swapLeftRight(root: TreeNode) -> TreeNode:
    # 如果树为空，直接返回
    if not root:
        return None

    # 交换左右子树
    root.left, root.right = root.right, root.left

    # 递归交换左右子树
    swapLeftRight(root.left)
    swapLeftRight(root.right)

    return root

我们可以将这个函数应用到一棵二叉树上。例如，假设我们有以下二叉树：

     1
   /   \
  2     3
 / \   / \
4   5 6   7

使用 `swapLeftRight` 函数交换左右子树后，得到以下二叉树：

     1
   /   \
  3     2
 / \   / \
7   6 5   4

相关问题

递归实现二叉树左右子树交换

可以通过递归实现二叉树左右子树交换，具体实现如下所示：

# 定义二叉树节点类
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` 函数，该函数通过递归实现了二叉树左右子树的交换。具体实现如下：

- 如果当前节点为空，则直接返回 `None`；
- 否则，我们先交换当前节点的左右子树；
- 然后，递归处理左子树和右子树；
- 最后，返回根节点。

通过以上递归处理，我们可以实现二叉树左右子树的交换。

非递归实现二叉树左右子树交换

二叉树左右子树交换可以使用非递归的方式实现，可以借助栈来完成。具体实现步骤如下：

1. 声明一个栈，将根节点入栈。
2. 循环遍历栈，直至栈为空。循环中的操作如下：
a. 出栈一个节点，将其左右子节点交换。
b. 如果其左子节点不为空，则将左子节点入栈。
c. 如果其右子节点不为空，则将右子节点入栈。

以下是具体的实现过程的 Python 代码示例：

def invert_tree(root):
    if not root:
        return None
    stack = [root]
    while stack:
        node = stack.pop()
        node.left, node.right = node.right, node.left
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return root

以上代码中，`root` 表示二叉树的根节点。函数 `invert_tree` 通过栈的方式遍历二叉树，并将每个节点的左右子树进行交换。最后返回根节点即可。