По заданному бинарному дереву найдите горизонтальное расстояние между двумя узлами на одном уровне, также считая положение, где узел отсутствует

Question

Позвольте мне быть очень ясным, что я не понимаю, что такое горизонтальное расстояние.

Но все же с моей точки зрения. Горизонтальное расстояние означает: отсутствующие или существующие узлы между заданными узлами на одном уровне.

В моем случае, когда я пытаюсь выяснить расстояние между 7 и 1, получаю вывод, т.е. 2. Вот почему я думаю так, как упомянуто выше.

Но если я попытаюсь выяснить расстояние между 9 & 6, получаю вывод как 4.

Например, в данном дереве расстояние между узлами7 и 1, которые находятся на одном уровне, равны 2 (с учетом правого дочернего узла 2 и левого дочернего узла 3)

Это изображение поможет вам понять

И ниже приведен код, который я использую для проверки расстояния.

    public class BinaryHorizontalDistance
{
    public int findDistance(Node root, int n1, int n2) 
    {

    int leftNodeToRootNode = Pathlength(root, n1, "leftNodeToRootNode") - 2;
    int rightNodeToRootNode = Pathlength(root, n2,"rightNodeToRootNode") - 2;
    int lcaData = findLCA(root, n1, n2).data;   //LCA->Lowest Common Ancestor
    int lcaDistance = Pathlength(root, lcaData,"lcaDistance") - 1;
    return (leftNodeToRootNode + rightNodeToRootNode) - 2 * lcaDistance;

    }

    public int Pathlength(Node root, int n1,String callingFrom) 
    {

    if (root != null) 
    {

        int x = 0;

        if("rightNodeToRootNode" == callingFrom)
        {

            if(root.left ==null && root.right ==null)
            {
                //do nothing

            }
            else if(root.left ==null || root.right ==null)
            {
                System.out.println("counting the position where the node is not present is : "   +   root.data);
            }
            if ((root.data == n1) || (x = Pathlength(root.left, 
               n1,"rightNodeToRootNode")) > 0  || (x = Pathlength(root.right, 
               n1,"rightNodeToRootNode")) > 0) 
            {
                return x + 1;
            }
        }
        if("rightNodeToRootNode" != callingFrom )
        {

            if ((root.data == n1) || (x = Pathlength(root.left, 
            n1,"leftNodeToRootNode")) > 0  || (x = Pathlength(root.right, 
            n1,"leftNodeToRootNode")) > 0) 
            {
                return x + 1;
            }
        }

        return 0;
    }
    return 0;
}

public Node findLCA(Node root, int n1, int n2) 
{

    if (root != null)
    {

        if (root.data == n1 || root.data == n2) 
        {
            return root;
        }
        Node left = findLCA(root.left, n1, n2);
        Node right = findLCA(root.right, n1, n2);

        if (left != null && right != null)
        {
            return root;
        }
        if (left != null) 
        {
            return left;
        }
        if (right != null)
        {
            return right;
        }
    }
    return null;
}

public static void main(String[] args) throws java.lang.Exception 
{

    Node root = new Node(5);
    root.right = new Node(2);
    root.left = new Node(3);
    root.right.right = new Node(7);
    //root.right.left = new Node(78);
    root.right.right.right = new Node(9);
    root.left.left = new Node(1);
    //root.left.right = new Node(22);
    root.left.left.right = new Node(4);
    root.left.left.left = new Node(6);

    BinaryHorizontalDistance binaryTreeTest = new BinaryHorizontalDistance();
    System.out.println("Distance between 7 and 1 is : " + 
    binaryTreeTest.findDistance(root,9, 6));
    }

}

class Node 
{
int data;
Node left;
Node right;

    public Node(int data) 
    {
    this.data = data;
    this.left = null;
    this.right = null;
    }
}

Будет полезно получить пояснение с примером. И с удовольствием объясню дальше

Answer 1

вы знаете определение:

• , если вы левый ребенок: считать -1,
• , если вы правый ребенок: считать + 1

        5
      /   \
     4     6

здесь, для вычисления h(4,6)

• 4 - левый потомок 5: -1
• 6 - правый потомок 5: + 1

ч (4,6) = 0

        5
      /   \
     4     6
      \ 
       2

здесь, чтобы вычислить h(2,6), 2 вправо дочерний элемент 4 (** )очевидно, , если узел - единственный дочерний элемент, его следует рассматривать как правильный дочерний элемент):

поэтому h(2,4)=+1 вспомните h(4,6)=0 так h(2,6) = 1

относительно одного из ваших примеровскажем, h(9,6)

h(9,7) = 2
h(2,3) = 0
h(3,1) = 1 (1 only child so +1)
h(1,6) = 1 (same)
total: 4

** Я полагаю, +1 был выбран для согласованности, но я только что наблюдал это