题目一：二叉树基本算法的实现 ❖ 功能要求： ➢键盘输入二叉树结点前序序列，创建一棵二叉 树➢实现SwapTree方法，以根结点为参数，交换 每个结点的左子树和右子树（提示：前序递归 ）➢实现Find方法，查找值为key的结点，并输出 该结点的所有祖先结点

题目一所描述的是关于二叉树的基本操作，主要包括三个部分：

1. **创建二叉树**：通过用户输入的前序遍历序列，可以重构出二叉树结构。前序遍历（Root-Left-Right）的特点是先访问根节点，然后遍历左子树，最后遍历右子树。这个过程通常涉及递归，从第一个元素开始，作为当前节点，剩下的元素分别用于构建左右子树。

2. **SwapTree方法**：此函数接收二叉树的根节点作为参数，其目的是交换每个节点的左子树和右子树。由于前序遍历的特性，我们可以在递归过程中判断当前节点是否还有子节点，并在适当的时候交换它们的位置。这需要对二叉树的结构有深入理解，并利用递归的性质。

3. **Find方法**：查找给定键值（key）的结点并输出所有祖先节点。搜索过程通常是从根节点开始，如果找到目标节点则返回，否则继续向下遍历直到达到叶子节点。如果节点值等于key，那么祖先节点就是路径上除了当前节点外的所有节点。

以下是简单的伪代码示例：

# 假设Node类有left, right和val属性
class Node:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val

def build_tree(preorder):
    # 建立前序遍历到二叉树的映射
    root = create_node_from_preorder(preorder)
    return root

def create_node_from_preorder(preorder):
    if preorder:
        root_val = preorder.pop(0)  # 取出根节点
        root = Node(root_val)
        root.left = create_node_from_preorder(preorder)
        root.right = create_node_from_preorder(preorder)
        return root
    else:
        return None

def swap_tree(root):
    if root is not None:
        swap_tree(root.left), swap_tree(root.right)
        root.left, root.right = root.right, root.left

def find_ancestors(root, key):
    ancestors = []
    search(root, key, ancestors)
    return ancestors

def search(node, key, ancestors):
    if node is None or node.val == key:
        return ancestors
    ancestors.append(node.val)
    left_result = search(node.left, key, ancestors)  # 如果左子节点存在，则继续搜索
    if left_result:
        return left_result
    return search(node.right, key, ancestors)  # 否则在右子节点中寻找