多个序列确定树

给出多个不同的遍历序列, 要求确定二叉树.

先序遍历序列和中序遍历序列

先序遍历序列的第一个元素一定是根节点, 然后在中序中依据根节点可以找出左右子树, 然后就可以递归得出树的结构.

// CreateTreeByPreAndIn 使用前序遍历和中序遍历创建树结构
func CreateTreeByPreAndIn(preOrder, inOrder []int) *Node {
    if len(preOrder) == 0 || len(inOrder) == 0 {
        return nil
    }
    data := preOrder[0]
    index := 0
    for index < len(inOrder) {
        if inOrder[index] == data {
            break
        }
        index++
    }
    inOrderLeft, inOrderRight := inOrder[:index], inOrder[index+1:]
    preOrderLeft, preOrderRight := preOrder[1:len(inOrderLeft)+1], preOrder[1+len(inOrderLeft):]
    return &Node{
        data:  data,
        left:  CreateTreeByPreAndIn(preOrderLeft, inOrderLeft),
        right: CreateTreeByPreAndIn(preOrderRight, inOrderRight),
    }
}

后序遍历序列和中序遍历序列和以上差不多, 只不过是最后一个节点是根节点, 所以不过多赘述.

层次遍历序列和中序遍历序列

和前序序列相似, 在层次序列中, 开头的第一个元素是当前的根节点, 然后依然可以在中序序列中找到左右子树.这个时候就有不同了, 因为层次序列中的左右子树的节点分布是散开的, 并不是连续的, 所以我们需要遍历一遍数组, 将左右子树的节点分开到另外两个列表中 , 然后再递归构建树的结构.

// CreateTreeByLevelAndIn 使用层次遍历和中序遍历创建树结构
func CreateTreeByLevelAndIn(levelOrder, inOrder []int) *Node {
    if len(levelOrder) == 0 || len(inOrder) == 0 {
        return nil
    }
    data := levelOrder[0]
    index := 0
    levelOrderLeft, levelOrderRight := []int{}, []int{}
    for index < len(inOrder) {
        if inOrder[index] == data {
            break
        }
        index++
    }
    inOrderLeft, inOrderRight := inOrder[:index], inOrder[index+1:]
    for _, x := range levelOrder {
        mark := "right"
        for _, y := range inOrderLeft {
            if x == y {
                levelOrderLeft = append(levelOrderLeft, x)
                mark = "left"
            }
        }
        if mark == "right" {
            levelOrderRight = append(levelOrderRight, x)
        }
    }
    return &Node{
        data:  data,
        left:  CreateTreeByPreAndIn(levelOrderLeft, inOrderLeft),
        right: CreateTreeByPreAndIn(levelOrderRight, inOrderRight),
    }
}

前序序列和后序序列相同

不可以实现

多个序列估计二叉树

• pre 和 post 相同: T(LR) (LR)T
• pre 和 in 相同: T(L)R (L)TR
• in 和 post 相同: LT(R) L(R)T
• pre 和 post 相反: TLR LRT
• pre 和 in 相反: TL(R) LT(R)
• in 和 post 相反: (L)TR (L)RT