如何使用 Java 创建二叉树最大深度中包含的节点的链表
我已经创建了二叉树和链接列表类，我只需要一种仅打印最大路径的节点的算法。二叉树的高度和大小已经存储在根节点中，但我的问题是在将每个节点添加到链表时仅遍历最大路径。
I've already created the Binary Tree and Linked list classes, I'm just in need of an algorithm that prints ONLY the nodes of the largest path. The height and size of the Binary Tree are already stored in the root node, but my problem is traversing only the largest path while adding each node to my linked list.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我假设您的二叉树节点有对其父节点的引用，对吗？然后，您可以使用广度优先搜索或深度优先搜索并查找深度等于最大深度的根节点。一旦找到一个这样的节点，然后从那里沿着父节点的轨迹向上，并将沿途的每个节点添加到链接列表中。当到达顶部时，链表就有了最大路径的所有节点。
该算法如下所示：
请注意，节点的顺序是从叶节点到根节点 - 如果需要反转它，可以在最后一步之后执行此操作。
I assume your binary tree nodes have a reference to their parent, is that right? Then you could use either a breadth-first search or a depth-first search and find root nodes where the depth is equal to the max depth. Once you find one such node, then from there go up the trail of parent nodes, and add each node along the way to your linked list. When you reach the top, then the linked list has all the nodes of the largest path.
This algorithm would look like this:
Note that the order of the nodes is from the leaf node to the root - if you need to reverse it, you can do so after the last step.
我们制作一个二叉树数据结构，用一些虚拟数据填充它，以深度或广度优先搜索的方式遍历树，并构造最长路径中节点的链表。
网上有大量伪代码和更多信息：
http://en.wikipedia.org/wiki/Binary_tree< /a>
http://en.wikipedia.org/wiki/Linked_list
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search
我假设您已经了解 Java 并且还没有开始完全从头开始？
如果您在 Java 方面遇到困难，那么 Objects First with Java 是一本很棒的书，而且< a href="http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=3440" rel="nofollow noreferrer">算法简介似乎是标准书关于算法，可能非常值得一看。
Well make a binary tree data structure, fill it with some dummy data, traverse the tree with a depth or breadth first search and construct a linked list of the nodes in the longest path.
There's plenty of pseudo code and further information online:
http://en.wikipedia.org/wiki/Binary_tree
http://en.wikipedia.org/wiki/Linked_list
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search
I assume you already understand Java and are not starting completely from scratch?
If you're struggling with Java then Objects First with Java is a great book and also Introduction to Algorithms seems to be the standard book on algorithms and may be well worth looking at.