从前序与中序遍历序列构造二叉树

Construct Binary Tree from Preorder and Inorder Traversal

二叉树

2025/10/16

思路：从先序遍历为基础，一步步构造，如有不确定，参照中序遍历的信息。可以递归。

手写代码：


def DFS(preorder, inorder):

    if preorder == []:
        return None

    val = preorder[0]
    T = Node(val, None, None)
    id = inorder.index(val)
    N = len(preorder)

    left_length = id
    right_length = N -left_length - 1
    T.left = DFS(preorder[1:left_length], inorder[:id-1])
    T.right = DFS(preorder[left_length+1, :], inorder[id+1:])

    return T

评价：完全正确，有点麻烦，但是比较模版化

Back to top