The traditional recursive method is to find all the top-level parent nodes, loop through getChild(), and recursively call getChild() in getChild().

The complexity is n + n (the number of all child nodes), the first n is the number of times to find out all the parent nodes, and n (the number of parent nodes + the number of all child nodes) means that the collection will determine whether there are child nodes every time. If the set is a complete tree structure, then the number of parent nodes + all children nodes = n, that is, the number of calculations is n^2 + n, and the big O notation is O(n^2).

Here’s what I do: A double-layer for loop matches the children and filters out all the children in the set. The code is as follows:

@Data
public class CommentTreeRespDto implements Serializable {

    private static final long serialVersionUID = 9098462797193334657L;

    @ApiModelProperty(value = "Comment parent ID, top parent ID is 00000-00000-00000-00000")
    private String parentId;

    @ApiModelProperty(value = "Id of current log comment")
    private String id;

    @ApiModelProperty(value = "Comment content")
    private String content;

    @JsonFormat(pattern = "yyyy-MM-dd HH:mm:ss", timezone = "GMT+8")
    private Date createdDate;

    @ApiModelProperty(value = "Critic")
    private String createdBy;

    @ApiModelProperty(value = "Sub-comment under current comment")
    private List<CommentTreeRespDto> childCommentList;
}
Copy the code
    public List<CommentTreeRespDto> getComment(IdBean<String> id) {
        List<CommentTreeRespDto> comment = queryDao.executeForObjectList("selDiaComByDiaId", id);
        comment.forEach(c -> {
            comment.forEach(m -> {
                if (c.getId().equals(m.getParentId())) {
                    if(! CollectionUtils.isEmpty(c.getChildCommentList())) { c.getChildCommentList().add(m); }else{ List<CommentTreeRespDto> cs = Lists.newArrayList(); cs.add(m); c.setChildCommentList(cs); }}}); });return comment.stream()
                .filter(e->(e.getParentId().equals(PARENT_ID)))
                .collect(Collectors.toList());
    }
Copy the code

The way I do it

  1. Easy to understand, a two-layer for loop is a little bit easier to understand than recursion, using the properties of sets.
  2. Simple code, with Java8 Stream + lambda expression, the introduction is easy to understand.
  3. In the complete tree structure, the time complexity is the same. N ^2 of the two-layer for loop + n of the filter child.

Feel free to leave your thoughts in the comments. We communicate with each other

Every time I grow up, I want to share with you. (Whisper BB, the public number used for the lottery.)