如何停止二进制搜索树遍历

Question

我需要遍历一个二进制搜索树并返回一个叶节点数组。目前，我正在遍历整个树，每次返回一个节点。

我的树看起来像：

10. Captain Picard
/                  
6. Commander Riker       11. Commander Data
/                        
4. Lt. Cmdr.   7. Lt. Cmdr.     12. Lt. Cmdr.
Worf           LaForge           Crusher
                           
5. Lieutenant                  13. Lieutenant
security-officer                    Selar

到目前为止，我有：

findOfficersWithNoDirectReports(values = []) {
if (this.officerName === null) return;
if (this.leftReport) {
this.leftReport.findOfficersWithNoDirectReports(
this.leftReport.officerName
);
}
if (this.rightReport) {
this.rightReport.findOfficersWithNoDirectReports(
this.rightReport.officerName
);
}
return values;
}

我的类构造函数有：officerId、officerName、reportTo、LeftReport、rightReport。如果Iconsole.log(this)，它看起来像：

StarshipEnterprise {
officerId: 10,
officerName: 'Captain Picard',
reportTo: null,
leftReport: StarshipEnterprise {
officerId: 6,
officerName: 'Commander Riker',
reportTo: [Circular],
leftReport: StarshipEnterprise {
officerId: 4,
officerName: 'Lt. Cmdr. Worf',
reportTo: [Circular],
leftReport: null,
rightReport: [StarshipEnterprise]
},
rightReport: StarshipEnterprise {
officerId: 7,
officerName: 'Lt. Cmdr. LaForge',
reportTo: [Circular],
leftReport: null,
rightReport: null
}
},
rightReport: StarshipEnterprise {
officerId: 11,
officerName: 'Commander Data',
reportTo: [Circular],
leftReport: null,
rightReport: StarshipEnterprise {
officerId: 12,
officerName: 'Lt. Cmdr. Crusher',
reportTo: [Circular],
leftReport: null,
rightReport: [StarshipEnterprise]
}
}
}

我应该得到：

["Lieutenant Security-Officer",
"Lt. Cmdr. LaForge",
"Lieutenant Selar"]

要返回此叶节点数组，当leftReport和rightReport是null时，如何停止树遍历？

Answer 1

findOfficersWithNoDirectReports() {
// If this is a leaf node, return the officer name
if (!this.leftReport && !this.rightReport) {
return [this.officerName]
}
// Otherwise, combine the left and right results 
val result = []
if (this.leftReport) {
result = result.concat(this.leftReport.findOfficersWithNoDirectReports());
}
if (this.rightReport) {
result = result.concat(this.rightReport.findOfficersWithNoDirectReports());
}
return result;
}