Go实现数据结构与算法之扁平数组转Tree

[WGrape]

一、介绍

给定一个扁平数组，数组内每个对象的id属性是唯一的。每个对象具有pid属性，pid属性为0表示为根节点（根节点只有一个），其它表示自己的父节点id。
编写一段程序，输入为给定的扁平数组，输出要求为一个树结构，为其中每个对象增加children数组属性（里面存放child对象）。

解法有很多种，性能最优的方案最佳。可以不用处理输入输出，专注实现核心逻辑即可。

1、输入

[
  {"id": 1, "name": "部门1", "pid": 0},
  {"id": 2, "name": "部门2", "pid": 1},
  {"id": 3, "name": "部门3", "pid": 1},
  {"id": 4, "name": "部门4", "pid": 3},
  {"id": 5, "name": "部门5", "pid": 4},
  {"id": 6, "name": "部门6", "pid": 3}
]

2、输出

{
  "id": 1,
  "name": "部门1",
  "pid": 0,
  "children": [
    {
      "id": 2,
      "name": "部门2",
      "pid": 1,
      "children": []
    },
    {
      "id": 3,
      "name": "部门3",
      "pid": 1,
      "children": [
        {
          "id": 4,
          "name": "部门4",
          "pid": 3,
          "children": [
            {
              "id": 5,
              "name": "部门5",
              "pid": 4,
              "children": []
            }
          ]
        },
        {
          "id": 6,
          "name": "部门6",
          "pid": 3,
          "children": []
        }
      ]
    }
  ]
}

解法

package main

import (
	"encoding/json"
	"fmt"
)

type Input struct {
	Id   int
	Name string
	Pid  int
}

type Item struct {
	Id       int
	Name     string
	Pid      int
	Children []Item
}

func find(result Item, pid int, needAppendChild Item) Item {
	if result.Id == pid {
		result.Children = append(result.Children, needAppendChild)
		return result
	}

	if len(result.Children) > 0 {
		for index := range result.Children {
         
                         // 核心重点是 find 返回值赋值给 result.Children[index]
			result.Children[index] = find(result.Children[index], pid, needAppendChild)
		}
	}
	return result
}

func main() {
	str := `[
  {"id": 1, "name": "部门1", "pid": 0},
  {"id": 2, "name": "部门2", "pid": 1},
  {"id": 3, "name": "部门3", "pid": 1},
  {"id": 4, "name": "部门4", "pid": 3},
  {"id": 5, "name": "部门5", "pid": 4},
  {"id": 6, "name": "部门6", "pid": 3}
]`

	itemList := make([]Input, 0)
	_ = json.Unmarshal(([]byte)(str), &itemList)

	var result = Item{}
	for index, v := range itemList {
		if index == 0 {
			result = Item{
				Id:       v.Id,
				Name:     v.Name,
				Pid:      v.Pid,
				Children: nil,
			}
			continue
		}

		needAppendChild := Item{
			Id:       v.Id,
			Name:     v.Name,
			Pid:      v.Pid,
			Children: nil,
		}
		result = find(result, v.Pid, needAppendChild)
	}

	outputBytes, _ := json.Marshal(result)
	fmt.Println(string(outputBytes))

	fmt.Println(result)
}