1

我在 JS 中有这段代码，它将某种物化路径转换为树结构：

var input = [[1201], [1201,1202,1203,1204], [1201,1202,1203], [1201,1202], [1201,1205]];
var output = [];

for (var i = 0; i < input.length; i++) {
    var chain = input[i];
    var currentNode = output;
    for (var j = 0; j < chain.length; j++) {
        var wantedNode = chain[j];
        var lastNode = currentNode;
        for (var k = 0; k < currentNode.length; k++) {
            if (currentNode[k].name == wantedNode) {
                currentNode = currentNode[k].children;
                break;
            }
        }

        if (lastNode == currentNode) {
            var newNode = currentNode[k] = {name: wantedNode, children: []};
            currentNode = newNode.children;
        }
    }
}

它工作正常并给了我期望的结果：

[
  {
    "name": 1201,
    "children": [
      {
        "name": 1202,
        "children": [
          {
            "name": 1203,
            "children": [
              {
                "name": 1204,
                "children": []
              }
            ]
          }
        ]
      },
      {
        "name": 1205,
        "children": []
      }
    ]
  }
]

但是我在将它移植到 Go 时遇到了一些问题。迄今为止最接近的解决方案是：

type tree struct {
    ID       int     `json:"name"`
    Children []*tree `json:"children"`
}

func (t *tree) get(id int) *tree {
    for _, c := range t.Children {
        if c.ID == id {
            return c
        }
    }
    return nil
}

func (t *tree) hasChild(id int) bool {
    for _, c := range t.Children {
        if c.ID == id {
            return true
        }
    }
    return false
}



root := tree{}
var tmpRoot *tree
for _, chain := range input {
    if len(chain) == 1 {
        root.ID = chain[0]
        root.Children = make([]*tree, 0)
        tmpRoot = &root
    } else {
        // id := chain[len(chain)-1]
        parentID := chain[len(chain)-2]
        for i, id := range chain {
            if len(chain) < 2 || i == 0 {
                continue
            }

            if tmpRoot.ID == parentID {
                tmpRoot.Children = append(tmpRoot.Children, &tree{
                    ID:       id,
                    Children: make([]*tree, 0),
                })
            } else {
                if !tmpRoot.hasChild(id) {
                    tmpRoot = &tree{
                        ID:       id,
                        Children: make([]*tree, 0),
                    }
                    tmpRoot.Children = append(root.Children, tmpRoot)
                }
                tmpRoot = tmpRoot.get(id)
            }
        }
    }
}

但是在不同的输入上仍然缺少一些值，比如

[[1201], [1201, 1205], [1201, 1207], [1201, 1202], [1201, 1202, 1206], [1201, 1202, 1203], [1201, 1202, 1203, 1204], [1201, 1202, 1203, 1208]]

给我

{"name":1201,"children":[{"name":1205,"children":[]},{"name":1207,"children":[]},{"name":1202,"children":[{"name":1206,"children":[]},{"name":1202,"children":[]},{"name":1203,"children":[]}]}]}

任何帮助表示赞赏。

去游乐场： https: //play.golang.org/p/XIHbaDHkp0m

4

1 回答 1

0

完毕。这是工作代码：

type tree struct {
    ID       int     `json:"id"`
    Children []*tree `json:"children"`
}

func main() {
    input := [][]int{
        []int{1201}, 
        []int{1201, 1205}, 
        []int{1201, 1207}, 
        []int{1201, 1202}, 
        []int{1201, 1202, 1206}, 
        []int{1201, 1202, 1203}, 
        []int{1201, 1202, 1203, 1204}, 
        []int{1201, 1202, 1203, 1208},
        []int{1201, 1209},
        []int{1201, 1202, 1210},
    }
    output := make([]*tree, 0)

    for _, chain := range input {
        currentNode := &output

        for _, id := range chain {
            wantedNode := id
            lastNode := currentNode

            var k int
            for _, cn := range *currentNode {
                if cn.ID == wantedNode {
                    currentNode = &((*currentNode)[k].Children)
                    break
                }
                k++
            }

            if reflect.DeepEqual(lastNode, currentNode) {
                newNode := &tree{ID: wantedNode, Children: make([]*tree, 0)}
                *currentNode = append(*currentNode, newNode)
                currentNode = &newNode.Children
            }
        }
    }

    d, _ := json.Marshal(&output)
    fmt.Printf(string(d))
}

输出：

[
  {
    "id": 1201,
    "children": [
      {
        "id": 1205,
        "children": []
      },
      {
        "id": 1207,
        "children": []
      },
      {
        "id": 1202,
        "children": [
          {
            "id": 1206,
            "children": []
          },
          {
            "id": 1203,
            "children": [
              {
                "id": 1204,
                "children": []
              },
              {
                "id": 1208,
                "children": []
              }
            ]
          },
          {
            "id": 1210,
            "children": []
          }
        ]
      },
      {
        "id": 1209,
        "children": []
      }
    ]
  }
]
于 2019-03-16T19:55:18.267 回答