All geek questions in one place

How to create a linked list of nodes that are contained in the maximum depth of the binary tree using Java

I already created the Binary Tree and Linked list classes, I just need 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 directory of the node, but my problem is moving only the largest path when adding each node to my linked list.

0
source share
2 answers

I assume your binary tree nodes have a reference to their parent, right? Then you can use a width search or depth search and find the root nodes where the depth is equal to the maximum depth. Once you find one such node, then follow the path of the parent nodes from there and add each node along the path to your linked list. When you reach the top, the linked list has all the nodes of the largest path.

This algorithm will look like this:

  • start with a binary tree root
  • use width or depth search to reach leaf nodes (nodes that do not have child nodes)
    • when you reach the leaf node, check its depth:
      • if it is not equal to the maximum depth, ignore it and continue the search
      • , node ( , , ).
  • node , parent
  • , node, , .

, node - , .

+2

Source: https://habr.com/ru/post/1751871/

More articles:


All Articles