Самый длинный путь между 2 Узлами

Правильный алгоритм:

1. Запустите DFS с любого узла, чтобы найти самый дальний листовой узел. Обозначьте этот узел T.
2. Запустите еще одну DFS, чтобы найти самый дальний узел от T.
3. Путь, который вы нашли на шаге 2, является самым длинным путем в дереве.

Этот алгоритм определенно будет работать, и вы также не ограничены только двоичными деревьями. Я не уверен насчет вашего алгоритма:

Я прав, говоря, что путем нахождения самого длинного пути среди корня, его левого и правого узлов, а затем рекурсии на его левом и правом узлах, передавая им самый длинный путь из предыдущего вызова метода и наконец (когда ???) вернуть самый длинный путь, я не уверен, как вы собираетесь его вернуть ...

потому что я не понимаю, что именно вы описываете. Можете ли вы проработать это вручную на примере или попытаться лучше объяснить? Так вы сможете лучше понять, правильно это или нет.

Похоже, вы пытаетесь рекурсивно реализовать в основном то же самое, только упрощенное для двоичных деревьев. Однако ваш код кажется довольно сложным для этой проблемы. Просмотрите обсуждение здесь для более простой реализации.

Мне кажется, вы слишком усложняете задачу.

Подумайте о самом длинном пути, который проходит через узел n и не поднимается к родителю n. Какая связь между длиной этого пути и высотами обоих поддеревьев, соединенных с n?

Выяснив это, проверьте дерево рекурсивно, рассуждая следующим образом:

Самый длинный путь для поддерева с корнем n - это самый длинный путь из следующих трех:

1. Самый длинный путь в поддереве, корнем которого является n. left_child
2. Самый длинный путь в поддереве, корнем которого является n.right_child
3. Самый длинный путь, который проходит через узел n и не поднимается к родителю n

Что, если для каждого узла n вашей целью было вычислить эти два числа:

• f ( n ): длина самого длинного путь в дереве с корнем n
• h ( n ): высота дерева с корнем в n .

Для каждого конечного узла (узлов, имеющих нулевой левый и правый узлы), очевидно, что f и h оба равны 0.

Теперь h каждого узла n ] равно:

• 0, если n.left и n.right оба равны null
• 1 + h ( n.left ) если только n.left не- null
• 1 + h ( n.right ), если только n.right не- null
• 1 + max (h ( n.left ), h ( n.right )), если оба n.left и ] n.right не - null

И f ( n ) равно:

• 0, если n.left и n. right оба null
• max (f ( n.left ), h ( n )), если только n.left не - null
• ?? если только п.right не - null
• ?? если оба n.left и n.right не являются null

(Вам нужно выяснить, что заменяет два заполнителя "??". Есть варианты которые заставляют эту стратегию работать. Я испытал ее лично.)

Тогда longestPath (Node n) - это просто f ( n ):

public class SO3124566
{
    static class Node
    {
        Node left, right;

        public Node()
        {
            this(null, null);
        }

        public Node(Node left, Node right)
        {
            this.left = left;
            this.right = right;
        }
    }

    static int h(Node n)
    {
        // ...
    }

    static int f(Node n)
    {
        // ...
    }

    public static int longestPath(Node n)
    {
        return f(n);
    }

    public static void main(String[] args)
    {
        { // @phimuemue's example
            Node n6 = new Node(),
                n9 = new Node(),
                a = new Node(),
                n7 = new Node(n9, a),
                n4 = new Node(n6, n7),
                b = new Node(),
                n8 = new Node(null, b),
                n5 = new Node(null, n8),
                n2 = new Node(n4, n5),
                n3 = new Node(),
                n1 = new Node(n2, n3);
            assert(longestPath(n1) == 6);
        }{ // @Daniel Trebbien's example: http://pastebin.org/360444
            Node k = new Node(),
                j = new Node(k, null),
                g = new Node(),
                h = new Node(),
                f = new Node(g, h),
                e = new Node(f, null),
                d = new Node(e, null),
                c = new Node(d, null),
                i = new Node(),
                b = new Node(c, i),
                a = new Node(j, b);
            assert(longestPath(a) == 8);
        }



        assert(false); // just to make sure that assertions are enabled.
            // An `AssertionError` is expected on the previous line only.
    }
}

Вы должны быть в состоянии напишите рекурсивные реализации f и h, чтобы этот код работал; однако это решение ужасно неэффективно. Его цель - просто понять расчет.

Чтобы повысить эффективность, вы можете использовать мемоизацию или преобразовать это в нерекурсивное вычисление, использующее стек (ы).