023.二叉树的高度

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

题目描述

现给定一棵二叉树的先序遍历序列和中序遍历序列，要求你计算该二叉树的高度。

输入描述

输入包含多组测试数据，每组输入首先给出正整数N（⇐50），为树中结点总数。下面2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

输出描述

对于每组输入，输出一个整数，即该二叉树的高度。

输入示例

9
ABDFGHIEC
FDHGIBEAC
7
Abcdefg
gfedcbA

输出示例

5
7

答案

package main
 
import (
    "bufio"
    "os"
    "fmt"
    "strconv"
)
 
var (
    n int
    preorder []byte
    inorder []byte
    root *BinaryTreeNode
)
 
func main() {
    input := bufio.NewScanner(os.Stdin)
    for input.Scan() {
        n, _ = strconv.Atoi(input.Text())
        input.Scan()
        preorder = []byte(input.Text())
        input.Scan()
        inorder = []byte(input.Text())
        root = buildBinaryTree(preorder, inorder)
        fmt.Println(getMaxHeigth(root))
    }
}
 
type BinaryTreeNode struct {
    Val byte
    Left *BinaryTreeNode
    Right *BinaryTreeNode
}
 
func buildBinaryTree(preorder, 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 := getIdx(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 getIdx(arr []byte, target byte) int {
    for i, v := range arr {
        if v == target {
            return i
        }
    }
    return -1
}
 
func getMaxHeigth(root *BinaryTreeNode) int {
    res := 0
    queue := []*BinaryTreeNode{}
    if root != nil {
        queue = append(queue, root)
    }
    for len(queue) > 0 {
        size := len(queue)
        res++
        for i := 0; i < size; i++ {
            cur := queue[i]
            if cur.Left != nil {
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue, cur.Right)
            }
        }
        queue = queue[size:]
    }
    return res
}