如何使用Java创建包含在二叉树的最大深度中的节点的链表 [英] How to create a linked list of nodes that are contained in the max-Depth of a Binary Tree using Java

问题描述

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

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.

推荐答案

我假设您的二叉树节点有对其父节点的引用，对吗?然后，您可以使用广度优先搜索或深度优先搜索来查找深度等于最大深度的根节点.一旦找到一个这样的节点，就从那里沿着父节点的踪迹前进，然后将每个节点添加到链接列表中.当您到达顶部时，链接列表将包含最大路径的所有节点.

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.

此算法如下所示:

1. 从二叉树的根开始
2. 使用广度优先或深度优先搜索到达叶节点(没有任何子节点的节点)

1. start at the root of the binary tree
2. use a breadth-first or depth-first search to reach leaf nodes (nodes which do not have any children nodes)

1. 到达叶节点时，请检查其深度:

1. when you reach a leaf node, check it's depth:

1. 如果它不等于最大深度，请忽略它并继续搜索
2. 如果它等于最大深度，则您已找到最大路径的末端节点(可以有多个路径，但此时区分它们似乎并不重要).转到下一步

将此叶子节点添加到链接列表，然后转到其父节点

重复最后一步，直到到达根节点并且没有父节点为止-链表中所有节点的路径最长.

请注意，节点的顺序是从叶节点到根节点-如果需要反转它，则可以在最后一步之后进行.

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.

这篇关于如何使用Java创建包含在二叉树的最大深度中的节点的链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！