题解 | #二叉树遍历#

以不变应万变，搞清楚原理很重要。

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


def solve(preorder, inorder):
    if not preorder:
        return None
    left_size = inorder.index(preorder[0])
    left = solve(preorder[1 : left_size + 1], inorder[0:left_size])
    right = solve(preorder[left_size + 1 :], inorder[left_size + 1 :])
    return TreeNode(preorder[0], left, right)


def dfs(node):
    if not node:
        return
    dfs(node.left)
    dfs(node.right)
    print(node.val, end="")


while True:
    try:
        preorder = input()
        inorder = input()
        root = solve(preorder, inorder)
        dfs(root)
        print()
    except:
        break