在某OS的文件系统中（同一目录下的目录和文件不会重名），假设当前目录为根目录，给定若干个已有路径（目录或文
件），其格式如下：
· 输入均为根目录下的路径，且不会重复给出；
· 路径中目录或文件名仅包含字母、数字和分隔符/；
· 路径结尾带/表示目录，否则是文件。例如 var/log/是目录，etc/profile是文件。
请按照以下规则，将输入的路径整理成树状结构并输出：
· 同一父目录下的目录或文件按字典序升序输出，大小写敏感
· 第一层目录或文件无需缩进；后续每深入一层，需要多缩进两个空格
· 输出时目录和文件都不含/
解答要求时间限制：1000ms, 内存限制：256MB
输入
第一行一个整数 num，表示路径的数量，取值范围 [1,1000]
接下来 num 行，每行一个路径字符串，长度范围 [1,255]
用例保证输入的路径合法，且不会以/开头
输出
按行输出树状结构的路径
样例
输入样例 1
5
usr/local/lib64
GAMES
usr/DRIVERS
home
var/log/
输出样例
GAMES
home
usr
DRIVERS
local
lib64
var
log
提示样例 1
输出内容，及对应的路径，如下图所示：
输入样例 2
4
ROOT/A
drv
root/b/
ROOT/
输出样例
ROOT
A
drv
root
b
大小写敏感，所以ROOT 和 root 是两个目录，按字典序大写在前。
2. 题目分析
题目理解：
题目要求将扁平的目录结构，转换为层状显示，例如输入：
usr/local/lib64
usr/DRIVERS
要求输出：
usr
DRIVERS
local
lib64
题目说了，同一目录下的目录和文件不会重名，意味着不同路径下可能存在同名目录、文件。
关键需求分析：
l 由于一行输入的路径可能包含分隔符’/’、需要拆分为多个路径，所以输出的行数可能比输入行数多。
l 同一父目录下的目录或文件按字典序升序输出，即按’/’拆分前就需要排序，输出后的路径的归属关系不能打乱。
l 当前行路径和上一行路径前面相同部分不输出、而是以空格代替。
解题思路：
主要有两种思路：
1) 构造、遍历树
涉及到路径操作的问题，通常可以用树这种数据结构，所以容易想到的解法就是定义一个树的结构，例如：
struct Node {
节点名称;
Node *children; 子节点
} Node;
Node具体的成员定义有多种不同的实现方式，例如常见的有：
|
C++ |
Java |
Python |
Go |
|
class Node { public: string name; vector<Node> children; }; |
static class Trie { ... TreeMap<String, Trie> children; } |
class Tree: def __init__(self, val, level = 0): self.val = val self.level = level self.children = {} |
type Node struct { name string children Nodes idx map[string]int } |
根据输入参数构造出树后，再深度遍历就可以得到输出结果。
2) 按字符’/’拆分字符串后，生成一个映射表
根据题目样例1的提示，将输出和路径这两列的顺序调换一下，可以得到如下表格
|
唯一路径名 |
显示名称 |
|
usr |
usr |
|
usr/DRIVERS |
DRIVERS |
|
usr/local |
local |
|
usr/local/lib64 |
lib64 |
可以看到，只要我们整理出所有不重复的全路径名、排序之后，就可以得到第一列内容；然后再根据路径中’/’的个数计算空格的数量就得到最终的显示名称。
不重复的全路径名可以通过TreeMap/TreeSet/map/set/dict等容器来实现。
map建树+DFS遍历
package main
import (
"fmt"
"sort"
"strings"
)
type DirNode struct {
name string
level int
children []*DirNode
}
func buildTree(routeList []string, dirTreeList map[string]*DirNode) {
// 大小写敏感,拆分之前需排序,字典序升序
sort.Slice(routeList, func(i, j int) bool {
return routeList[i] < routeList[j]
})
for _, route := range routeList {
routeNameList := strings.Split(route, "/")
for index, routeName := range routeNameList {
if routeName != "" {
if _, exist := dirTreeList[routeName]; !exist {
dirTreeList[routeName] = &DirNode{
name: routeName,
level: index,
}
}
}
}
}
fmt.Println(dirTreeList)
}
type Node struct {
level int
child map[string]*Node
}
func NewNode(level int) *Node {
return &Node{
level: level,
child: make(map[string]*Node),
}
}
const G_BLANK_NUM = 2
func Dfs(root *Node, res *[]string) {
if len(root.child) == 0 {
return
}
var keys []string
for k := range root.child {
keys = append(keys, k)
}
sort.Strings(keys)
for _, k := range keys {
v := root.child[k]
blank := strings.Repeat(" ", root.level*G_BLANK_NUM)
cur := blank + k
*res = append(*res, cur)
if v != nil {
Dfs(v, res)
}
}
}
func GetTreeFormat(fileTreeList []string) []string {
root := NewNode(0)
for _, file := range fileTreeList {
names := strings.Split(file, "/")
cur := root
for _, name := range names {
if _, ok := cur.child[name]; !ok {
cur.child[name] = NewNode(cur.level + 1)
}
cur = cur.child[name]
}
}
var result []string
Dfs(root, &result)
return result
}
func main() {
routeList := []string{
"usr/local/lib64",
"GAMES",
"usr/DRIVERS",
"home",
"var/log/",
}
//dirTreeList := make(map[string]*DirNode, len(routeList))
//buildTree(routeList, dirTreeList)
//for _, dirTree := range dirTreeList {
// for i := 0; i < dirTree.level; i++ {
// fmt.Print(" ")
// }
// fmt.Println(dirTree.name)
//}
ans := GetTreeFormat(routeList)
for _, result := range ans {
fmt.Println(result)
}
}
View Code
map建多叉树总结：
func buildTree(parent, child string, treeNodeMap map[string]*TreeNode) {
father, ok := treeNodeMap[parent]
if !ok {
father = &TreeNode{name: parent}
treeNodeMap[parent] = father
}
children, ok := treeNodeMap[child]
if !ok {
children = &TreeNode{name: child}
treeNodeMap[child] = children
}
father.child = append(father.child, children)
}
变种1
func buildTree(pairs [][]string) *Node {
nodes := make(map[string]*Node)
for _, pair := range pairs {
parent, child := pair[0], pair[1]
if nodes[parent] == nil {
nodes[parent] = &Node{val: parent}
}
if nodes[child] == nil {
nodes[child] = &Node{val: child}
}
nodes[parent].children = append(nodes[parent].children, nodes[child])
}
return nodes["root"]
}
变种2
func buildTree(parent, child int, statuses []int, nodes map[int]*dirNode) {
if nodes[child] == nil {
nodes[child] = &dirNode{id: child, status: statuses[child], userId: map[int]bool{}}
}
if nodes[parent] == nil && parent != -1 {
nodes[parent] = &dirNode{id: parent, status: statuses[parent], userId: map[int]bool{}}
}
if parent != -1 {
nodes[parent].children = append(nodes[parent].children, nodes[child])
nodes[child].parent = nodes[parent]
}
}
变种3
root := NewNode(0)
for _, file := range fileTreeList {
names := strings.Split(file, "/")
cur := root
for _, name := range names {
if _, ok := cur.child[name]; !ok {
cur.child[name] = NewNode(cur.level + 1)
}
cur = cur.child[name]
}
}
建二叉树
// 构建二叉树
func buildTree(nodeValues []int) *Node {
if len(nodeValues) == 0 || nodeValues[0] == math.MaxInt32 {
return nil
}
root := &Node{value: rune(nodeValues[0])}
queue := []*Node{root}
i := 1
for len(queue) > 0 && i < len(nodeValues) {
node := queue[0]
queue = queue[1:]
// 左子节点
if nodeValues[i] != math.MaxInt32 {
node.left = &Node{value: nodeValues[i]}
queue = append(queue, node.left)
}
i++
// 右子节点
if i < len(nodeValues) && nodeValues[i] != math.MaxInt32 {
node.right = &Node{value: nodeValues[i]}
queue = append(queue, node.right)
}
i++
}
return root
}
标签：Node,上机,parent,编程,交流,child,nodes,root,string From： https://www.cnblogs.com/gongxianjin/p/17918611.html