java - 如何使用Java创建包含在二叉树的最大深度中的节点的链接列表

Question

我已经创建了二叉树和链表类，我只需要一个只打印最大路径节点的算法。二叉树的高度和大小已经存储在根节点中，但我的问题是在将每个节点添加到我的链表时只遍历最大路径。

score 2 · Accepted Answer

我假设您的二叉树节点引用了它们的父节点，对吗？然后您可以使用广度优先搜索或深度优先搜索并找到深度等于最大深度的根节点。一旦你找到一个这样的节点，然后从那里沿着父节点的踪迹前进，并将沿途的每个节点添加到你的链表中。当您到达顶部时，链表具有最大路径的所有节点。

这个算法看起来像这样：

从二叉树的根开始
使用广度优先或深度优先搜索到达叶节点（没有任何子节点的节点）
1. 当你到达叶节点时，检查它的深度：
  1. 如果它不等于最大深度，则忽略它并继续搜索
  2. 如果它等于最大深度，那么您已经找到了最大路径的结束节点（可能不止一个，但此时区分它们似乎并不重要）。进行下一步
将此叶节点添加到链表中，然后转到它的父节点
重复最后一步，直到到达根节点并且没有父节点 - 然后您的链表具有最长路径的所有节点。

注意节点的顺序是从叶子节点到根节点——如果需要倒序，可以在最后一步之后倒序。

score 0 · Accepted Answer

好吧，制作一个二叉树数据结构，用一些虚拟数据填充它，以深度或广度优先搜索遍历树并构造最长路径中节点的链表。

网上有很多伪代码和更多信息：

我假设您已经了解 Java 并且没有完全从头开始？

如果您在 Java 上苦苦挣扎，那么Objects First with Java是一本很棒的书，而且Introduction to Algorithms似乎是关于算法的标准书籍，可能非常值得一看。

2 回答 2