022.二叉树的遍历

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

题目描述

给出一个n个节点的二叉树，请求出二叉树的前序遍历，中序遍历和后序遍历。

输入描述

第一位一个整数 n(0<n⇐26)，表示二叉树有 n 个节点，以下 n 行，每行第一个为一个大写字母表示节点，后面为两整数，第一个表示左儿子序号，第二个表示右儿子序号，如果该序号为0表示没有。 (例如下面示例中，F 序号为1，C 序号为2，E 序号为3，A 序号为4，D 序号为5，G 序号为6，B 序号为7)

输出描述

共三行，第一行为二叉树的前序遍历，第二行为中序遍历，第三行为后序遍历

输入示例

7
F 2 3
C 4 5
E 0 6
A 0 0
D 7 0
G 0 0
B 0 0

输出示例

FCADBEG
ACBDFEG
ABDCGEF

答案

package main
 
import (
    "bufio"
    "os"
    "fmt"
    "strings"
    "strconv"
)
 
var (
    arr []string
    nodes []*BinaryTreeNode
    i int
    n int
    left int
    right int
)
 
func main() {
    input := bufio.NewScanner(os.Stdin)
    for input.Scan() {
        n, _ = strconv.Atoi(input.Text())
        if n <= 0 {
            continue
        }
        nodes = make([]*BinaryTreeNode, n + 1)
        for i = 1; i <= n; i++ {
            input.Scan()
            arr = strings.Fields(input.Text())
            if nodes[i] == nil {
                nodes[i] = &BinaryTreeNode{}
            }
            nodes[i].Val = arr[0][0]
            left, _ = strconv.Atoi(arr[1])
            right, _ = strconv.Atoi(arr[2])
            if left != 0 {
                if nodes[left] == nil {
                    nodes[left] = &BinaryTreeNode{}
                }
                nodes[i].Left = nodes[left]
            }
            if right != 0 {
                if nodes[right] == nil {
                    nodes[right] = &BinaryTreeNode{}
                }
                nodes[i].Right = nodes[right]
            }
        }
        printPreorder(nodes[1])
        fmt.Println()
        printInorder(nodes[1])
        fmt.Println()
        printPostorder(nodes[1])
        fmt.Println()
    }
}
 
type BinaryTreeNode struct {
    Val byte
    Left *BinaryTreeNode
    Right *BinaryTreeNode
}
 
func printPreorder(root *BinaryTreeNode) {
    if root == nil {
        return
    }
    fmt.Printf("%c", root.Val)
    printPreorder(root.Left)
    printPreorder(root.Right)
}
 
func printInorder(root *BinaryTreeNode) {
    if root == nil {
        return
    }
    printInorder(root.Left)
    fmt.Printf("%c", root.Val)
    printInorder(root.Right)
}
 
func printPostorder(root *BinaryTreeNode) {
    if root == nil {
        return
    }
    printPostorder(root.Left)
    printPostorder(root.Right)
    fmt.Printf("%c", root.Val)
}