设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写递归算法交换该二叉树的左右孩子。

可以按照以下步骤编写递归算法：

1. 如果二叉树为空，直接返回。

2. 如果二叉树非空，则交换当前节点的左右孩子。

3. 递归交换左子树。

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

这个算法的时间复杂度是 O(n)，其中 n 是二叉树节点的数量。因为每个节点只会被访问一次。空间复杂度是 O(h)，其中 h 是二叉树的高度。在最坏的情况下，二叉树退化成链表，此时空间复杂度为 O(n)。

相关问题

设二叉树中的每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写递归算法交换该二叉树的左右孩子

可以使用递归的方式来交换二叉树的左右孩子，具体实现如下：

1. 如果当前结点为空，则返回空。
2. 交换当前结点的左右孩子。
3. 递归交换当前结点的左子树。
4. 递归交换当前结点的右子树。
5. 返回交换后的二叉树根结点。

代码实现如下：

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

def swap_tree(root: TreeNode) -> TreeNode:
    if not root:
        return None
    
    root.left, root.right = root.right, root.left
    swap_tree(root.left)
    swap_tree(root.right)
    
    return root

时间复杂度为 O(n)，其中 n 是二叉树中的结点个数。

设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写递归算法实现该二叉树的双序遍历（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。

下面是递归算法实现二叉树的双序遍历：

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


def double_order_traversal(root: TreeNode):
    if root is None:
        return

    # 先访问当前结点
    print(root.val, end=' ')

    # 双序遍历左子树
    if root.left is not None:
        double_order_traversal(root.left)

    # 再次访问当前结点
    print(root.val, end=' ')

    # 双序遍历右子树
    if root.right is not None:
        double_order_traversal(root.right)

首先，我们先判断当前结点是否为空，如果为空则直接返回。否则，我们先访问当前结点，然后递归访问左子树，再次访问当前结点，最后递归访问右子树。这样就可以完成二叉树的双序遍历。