021.构造二叉树

时间限制：1.000S  空间限制：32MB

题目描述

给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。

输入描述

输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。

输出描述

对于每组输入，输出对应的二叉树的后续遍历结果。

输入示例

DBACEGF ABCDEFG
BCAD CBAD

输出示例

ACBFGED
CDAB

答案

package main
 
import (
    "bufio"
    "os"
    "fmt"
    "strings"
)
 
var (
    arr []string
    preorder []byte
    inorder []byte
    tree *BinaryTreeNode
)
 
func main() {
    input := bufio.NewScanner(os.Stdin)
    for input.Scan() {
        arr := strings.Fields(input.Text())
        preorder = []byte(arr[0])
        inorder = []byte(arr[1])
        tree = buildBinaryTree(preorder, inorder)
        printPostorder(tree)
        fmt.Println()
    }
}
 
type BinaryTreeNode struct {
    Val byte
    Left *BinaryTreeNode
    Right *BinaryTreeNode
}
 
func buildBinaryTree(preorder []byte, inorder []byte) *BinaryTreeNode {
    n1 := len(preorder)
    n2 := len(inorder)
    if n1 != n2 {
        panic("preorder and inorder len not equal")
    }
    if n1 == 0 {
        return nil
    }
    node := &BinaryTreeNode{ Val: preorder[0] }
    idx := findIdx(inorder, preorder[0])
    if idx == -1 {
        panic("preorder and inorder mismatch")
    }
    node.Left = buildBinaryTree(preorder[1:idx + 1], inorder[:idx])
    node.Right = buildBinaryTree(preorder[idx + 1:], inorder[idx + 1:])
    return node
}
 
func findIdx(arr []byte, target byte) int {
    for i, v := range arr {
        if v == target {
            return i
        }
    }
    return -1
}
 
func printPostorder(head *BinaryTreeNode) {
    if head == nil {
        return
    }
    printPostorder(head.Left)
    printPostorder(head.Right)
    fmt.Printf("%c", head.Val)
}