java怎么用递归返回树结构的结果？

Question

一、想要实现的效果

- 以搜索“秦朗为例”，最后返回的是 三国-曹操-秦朗 的一条链路（一棵树）。

二、我的代码
public class People {

private List<People> children;private String name;// 省略getter、setter方法

}
public static void main(String[] args) {

    People sunce = new People();    sunce.setName("孙策");    People sunquan = new People();    sunquan.setName("孙权");    People sunjian = new People();    sunjian.setName("孙坚");    sunjian.setChildren(Arrays.asList(sunce, sunquan));    People caopi = new People();    caopi.setName("曹丕");    People caozhi = new People();    caozhi.setName("曹植");    People caozhang = new People();    caozhang.setName("曹彰");    People qinlang = new People();    qinlang.setName("秦朗");    People caocao = new People();    caocao.setName("曹操");    caocao.setChildren(Arrays.asList(caopi, caozhi, caozhang, qinlang));    People liufeng = new People();    liufeng.setName("刘封");    People liushan = new People();    liushan.setName("刘禅");    People liubei = new People();    liubei.setName("刘备");    liubei.setChildren(Arrays.asList(liufeng, liushan));    People liuxun = new People();    liuxun.setName("刘循");    People liuzhang = new People();    liuzhang.setName("刘璋");    liuzhang.setChildren(Arrays.asList(liuxun));    People liuyan = new People();    liuyan.setName("刘焉");    liuyan.setChildren(Arrays.asList(liuzhang));    People sanguo = new People();    sanguo.setName("三国");    sanguo.setChildren(Arrays.asList(sunjian, caocao, liubei, liuyan));    List<People> p1 = query(sanguo, "刘");    System.out.println(p1);    List<People> p2 = query(sanguo, "秦");    System.out.println(p2);    List<People> p3 = query(sanguo, "孙策");    System.out.println(p3);}public static List<People> query(People people, String name) {    List<People> result = new ArrayList<>();    // 这里要判空，但简写就省略了    if(people.getName().contains(name)) {        return Arrays.asList(people);    } else {        if(people.getChildren() != null) {            for (People p : people.getChildren()) {                result.addAll(query(p, name));            }        }    }    return result;}

三、代码执行结果

四、解释
我递归用的少，用起来有点不达意。上面自己写的递归方法虽然能实现递归效果，但问题很大。
4.1、我的方法返回的只是命中项，而不是一个树的结构（除非第一层就命中了）。
4.2、返回的树里没有剔除未命中项。

上述两点（4.1和4.2）能否同时做到？如果不能，请指教怎么实现4.1，感谢。

Answer 1

这个问题可以通过使用递归和合适的数据结构来解决。在Java中，我们可以使用树结构（或者更具体地说，是树的列表）来存储每个人物及其子女的信息。然后，我们可以使用递归来查找从根节点到目标节点的路径。

为了实现你的需求，你可能需要对你的People类进行一些修改。尤其是，你需要为每个人物维护一个子节点列表，而不是仅仅为曹操和刘备。同时，你需要创建一个方法来构建这个树结构。以下是一个可能的实现：

import java.util.*;public class People {    private String name;    private List<People> children;    public People(String name) {        this.name = name;        this.children = new ArrayList<>();    }    public void addChild(People child) {        this.children.add(child);    }    public String getName() {        return this.name;    }    public List<People> getChildren() {        return this.children;    }}

然后，你可以在main方法中创建树结构：

public static void main(String[] args) {    // 创建节点    People sunjian = new People("孙坚");    People sunce = new People("孙策");    People sunquan = new People("孙权");    sunjian.addChild(sunce);    sunjian.addChild(sunquan);    People caocao = new People("曹操");    People caopi = new People("曹丕");    People caozhi = new People("曹植");    People caozhang = new People("曹彰");    caocao.addChild(caopi);    caocao.addChild(caozhi);    caocao.addChild(caozhang);    caocao.addChild(qinlang); // 这里需要添加 qinlang 节点，但你的代码中没有提供创建它的方法，我在这里添加它以便下面的代码可以运行。    // ... 其他节点创建方法类似，不再赘述。    // 构建树结构    People sanguo = new People("三国");    sanguo.addChild(sunjian);    sanguo.addChild(caocao);    // ... 添加其他节点 ...}

接下来，你可以使用递归方法来查找从根节点到目标节点的路径。以下是一个可能的实现：

public static List<People> query(People people, String name) {    List<People> result = new ArrayList<>();    if (people == null) {        return result;    } else if (people.getName().equals(name)) { // 找到目标节点，返回当前节点及其所有子节点（包括子节点的子节点等）        result.add(people);        result.addAll(people.getChildren()); // 包括当前节点的所有子节点。递归调用 query 方法，继续查找子节点的子节点。