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

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

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)

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

相关问题

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

可以使用递归算法实现二叉树左右孩子的交换，具体步骤如下：

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 root is None:
        return None
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root

该算法的时间复杂度为 O(n)，其中 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 是二叉树中的结点个数。