二叉树遍历(python)

解题思路:

注意事项:

参考代码:

# 定义树节点的数据结构

class TreeNode:

    def __init__(self, val):

        self.val = val

        self.left = None

        self.right = None

# 构建二叉树

def buildTree(inorder, levelorder):

    if not inorder or not levelorder:

        return None

    # 获取根节点的值

    root_val = levelorder[0]

    root = TreeNode(root_val)

    # 在中序遍历序列中找到根节点的位置

    root_idx = inorder.index(root_val)

    # 将中序遍历序列分为左子树和右子树

    inorder_left = inorder[:root_idx]

    inorder_right = inorder[root_idx + 1:]

    # 在按层遍历序列中找到左子树和右子树的节点值

    levelorder_left = [val for val in levelorder if val in inorder_left]

    levelorder_right = [val for val in levelorder if val in inorder_right]

    # 递归构建左子树和右子树

    root.left = buildTree(inorder_left, levelorder_left)

    root.right = buildTree(inorder_right, levelorder_right)

    return root

# 先序遍历二叉树

def preorderTraversal(root):

    if not root:

        return []

    result = []

    stack = [root]

    while stack:

        node = stack.pop()

        result.append(node.val)

        if node.right:

            stack.append(node.right)

        if node.left:

            stack.append(node.left)

    return result

# 主函数

def main():

    inorder = input().strip()  # 中序遍历序列

    levelorder = input().strip()  # 按层遍历序列

    # 构建二叉树

    root = buildTree(inorder, levelorder)

    # 先序遍历二叉树

    preorder = preorderTraversal(root)

    # 输出先序序列

    print(''.join(preorder))

# 调用主函数

main()