如何停止二叉搜索树遍历？

Question

我需要遍历一个二叉搜索树和return一个叶节点数组。目前我正在遍历整棵树并且一次return一个节点。

我的树看起来像：

                 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;
  }

我的 class 构造函数有：officerId、officerName、reportTo、LeftReport、rightReport。如果我 console.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"]

对于return这个叶节点数组，当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;

  }

如何停止二叉搜索树遍历？

How do I stop a Binary Search Tree Traversal?

javascript

algorithm

recursion

binary-search-tree

data-structures