golang-cookbook

Appearance

始终实现 ​

下面是使用 Go 实现 listToTree 的不同方法，并分析每个实现的时间复杂度。

1. 使用哈希表构建树（方法一） ​

这个方法利用哈希表来存储每个节点，之后通过 parentId 连接成树形结构。

Go 实现 ​

go
package main

import "fmt"

type Node struct {
	ID       int    `json:"id"`
	ParentID *int   `json:"parentId"`
	Name     string `json:"name"`
	Children []Node `json:"children,omitempty"`
}

func listToTree(items []Node) []Node {
	itemMap := make(map[int]Node)
	var root []Node

	// 将节点存入哈希表
	for _, item := range items {
		itemMap[item.ID] = item
	}

	// 将节点按父子关系连接
	for _, item := range items {
		if item.ParentID != nil {
			parent := itemMap[*item.ParentID]
			parent.Children = append(parent.Children, item)
			itemMap[*item.ParentID] = parent
		} else {
			root = append(root, item)
		}
	}

	return root
}

func main() {
	items := []Node{
		{ID: 1, ParentID: nil, Name: "A"},
		{ID: 2, ParentID: ptr(1), Name: "B"},
		{ID: 3, ParentID: ptr(1), Name: "C"},
		{ID: 4, ParentID: ptr(2), Name: "D"},
	}

	tree := listToTree(items)
	fmt.Println(tree)
}

func ptr(i int) *int {
	return &i
}

时间复杂度分析 ​

  • 构建哈希表: 将所有节点存储在哈希表中，需要遍历一次节点列表，所以时间复杂度是 O(n)。
  • 连接父子关系: 对于每个节点，需要查找父节点并将其添加到父节点的 children 列表中。这也是 O(n)，因为每个节点只会被遍历一次。

因此，总时间复杂度是 O(n)。

2. 递归构建树（方法二） ​

递归方法通过递归构建每个节点的子节点。

Go 实现 ​

go
package main

import "fmt"

type Node struct {
	ID       int    `json:"id"`
	ParentID *int   `json:"parentId"`
	Name     string `json:"name"`
	Children []Node `json:"children,omitempty"`
}

func listToTreeRecursive(items []Node, parentID *int) []Node {
	var tree []Node
	for _, item := range items {
		if item.ParentID == parentID {
			children := listToTreeRecursive(items, &item.ID)
			if len(children) > 0 {
				item.Children = children
			}
			tree = append(tree, item)
		}
	}
	return tree
}

func main() {
	items := []Node{
		{ID: 1, ParentID: nil, Name: "A"},
		{ID: 2, ParentID: ptr(1), Name: "B"},
		{ID: 3, ParentID: ptr(1), Name: "C"},
		{ID: 4, ParentID: ptr(2), Name: "D"},
	}

	tree := listToTreeRecursive(items, nil)
	fmt.Println(tree)
}

func ptr(i int) *int {
	return &i
}

时间复杂度分析 ​

  • 递归遍历: 对于每个节点，递归调用一次。递归的深度为树的高度，假设树的高度为 h。每次递归处理一个节点，因此时间复杂度为 O(n)（n 是节点数）。

因此，总时间复杂度是 O(n)。

3. 使用 DFS（深度优先搜索）（方法三） ​

DFS 方法使用递归或栈来遍历每个节点，并构建树。

Go 实现 ​

go
package main

import (
	"encoding/json"
	"fmt"
)

type Node struct {
	ID       int     `json:"id"`
	ParentID *int    `json:"parent_id"`
	Name     string  `json:"name"`
	Children []*Node `json:"children,omitempty"`
}

func listToTree(items []Node) []*Node {
	itemMap := make(map[int]*Node)
	var root []*Node

	for i := range items {
		itemMap[items[i].ID] = &items[i]
	}

	for i := range items {
		item := &items[i]
		if item.ParentID != nil {
			parent := itemMap[*item.ParentID]
			parent.Children = append(parent.Children, item)
		} else {
			root = append(root, item)
		}
	}

	return root
}

func main() {
	items := []Node{
		{ID: 1, ParentID: nil, Name: "A"},
		{ID: 2, ParentID: ptr(1), Name: "B"},
		{ID: 3, ParentID: ptr(1), Name: "C"},
		{ID: 4, ParentID: ptr(2), Name: "D"},
	}

	tree := listToTree(items)

	// 转换为 JSON
	jsonData, err := json.MarshalIndent(tree, "", "  ")
	if err != nil {
		fmt.Println("Error marshalling JSON:", err)
		return
	}

	fmt.Println(string(jsonData))
}

func ptr(i int) *int {
	return &i
}

时间复杂度分析 ​

  • DFS 遍历: 对于每个节点，递归调用一次，类似于递归方法，遍历树的每个节点，时间复杂度是 O(n)。

因此，总时间复杂度是 O(n)。

4. 使用 BFS（广度优先搜索）（方法四） ​

广度优先搜索方法通过队列逐层处理树的节点。

Go 实现 ​

go
package main

import "fmt"

type Node struct {
	ID       int    `json:"id"`
	ParentID *int   `json:"parentId"`
	Name     string `json:"name"`
	Children []Node `json:"children,omitempty"`
}

func listToTreeBFS(items []Node) []Node {
	itemMap := make(map[int]Node)
	var root []Node

	// 将节点存入哈希表
	for _, item := range items {
		itemMap[item.ID] = item
	}

	// 将根节点存入队列
	queue := make([]Node, 0)
	for _, item := range items {
		if item.ParentID == nil {
			queue = append(queue, item)
		}
	}

	// BFS 遍历树
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]

		for i, item := range items {
			if item.ParentID != nil && *item.ParentID == node.ID {
				node.Children = append(node.Children, item)
				queue = append(queue, item)
			}
		}
	}

	return root
}

func main() {
	items := []Node{
		{ID: 1, ParentID: nil, Name: "A"},
		{ID: 2, ParentID: ptr(1), Name: "B"},
		{ID: 3, ParentID: ptr(1), Name: "C"},
		{ID: 4, ParentID: ptr(2), Name: "D"},
	}

	tree := listToTreeBFS(items)
	fmt.Println(tree)
}

func ptr(i int) *int {
	return &i
}

时间复杂度分析 ​

  • BFS 遍历: 对于每个节点，遍历一次，并将子节点加入队列。每个节点最多被访问两次（一次是它本身，另一次是它的子节点）。因此，时间复杂度是 O(n)。

因此，总时间复杂度是 O(n)。

总结 ​

所有实现的时间复杂度都是 O(n)，因为每个节点只会被遍历一次。选择使用哈希表、递归、DFS 或 BFS 取决于具体应用场景以及个人偏好。