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

Ответ 1

Возможно, это так же просто:

public static int longestPath(Node n) {
    if (n != null) {
        return longestPath(n, 0); // forgot return?
    }
    return 0;
}

Его сложнее, чем можно было бы подумать с первого взгляда. Рассмотрим следующее дерево:

      1
     / \
    2   3
   / \
  4   5
 / \   \
6   7   8
   / \   \
  9   a   b

В этом случае корень node не находится даже в самом длинном пути (a-7-4-2-5-8-b).

Итак, вы должны сделать следующее: Для каждого node n вы должны вычислить следующее:

• вычислить самый длинный путь в левом поддереве, начиная с корня левого поддерева (называемого L)
• вычислить самый длинный путь в правом поддереве, начиная с корня правого поддерева (называемого R)
• вычислить самый длинный путь в левом поддереве (не обязательно начиная с корня левого поддерева) (называемый L)
• вычислить самый длинный путь в правом поддереве (не обязательно начиная с корня правого поддерева) (называемый R)

Затем определите, какая комбинация максимизирует длину пути:

• L+R+2, то есть переход от подпути в левом поддереве к текущему node и из текущего node через подпуть в правом поддереве
• L, т.е. просто взять левое поддерево и исключить текущий node (и, следовательно, правое поддерево) из пути
• R, т.е. просто взять правильное поддерево и исключить текущий node (и, следовательно, левое поддерево) из пути

Итак, я сделал бы небольшой взлом и для каждого node не вернул бы только один int, а тройку целых чисел, содержащих (L+R+2, l, r). Затем вызывающий должен решить, что делать с этим результатом в соответствии с приведенными выше правилами.

Ответ 2

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

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

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

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

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

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

Ответ 3

Вот мое рекурсивное решение в С++:

int longest_dis(Node* root) {
    int height1, height2;

    if( root==NULL)
        return 0;

    if( root->left == NULL ) && ( root->right == NULL )
        return 0;

    height1 = height(root->left); // height(Node* node) returns the height of a tree rooted at node
    height2 = height(root->right);

    if( root->left != NULL ) && ( root->right == NULL )
        return max(height1+1, longest_dis(root->left) );

    if( root->left == NULL ) && ( root->right != NULL )
        return max(height2+1, longest_dis(root->right) );

    return max(height1+height2+2, longest_dis(root->left), longestdis(root->right) );
}

Ответ 4

public int longestPath() {
    int[] result = longestPath(root);
    return result[0] > result[1] ? result[0] : result[1];
}

// int[] {self-contained, root-to-leaf}
private int[] longestPath(BinaryTreeNode n) {
    if (n == null) {
        return new int[] { 0, 0 };
    }
    int[] left = longestPath(n.left);
    int[] right = longestPath(n.right);

    return new int[] { Util.max(left[0], right[0], left[1] + right[1] + 1),
            Util.max(left[1], right[1]) + 1 };
}

Ответ 5

Простая реализация:

int maxDepth(Node root) {
    if(root == null) {
        return 0;
    } else {
        int ldepth = maxDepth(root.left);
        int rdepth = maxDepth(root.right);
        return ldepth>rdepth ? ldepth+1 : rdepth+1;
    }
}

int longestPath(Node root)
{
   if (root == null)
     return 0;

  int ldepth = maxDepth(root.left);
  int rdepth = maxDepth(root.right);

  int lLongPath = longestPath(root.left);
  int rLongPath = longestPath(root.right);

  return max(ldepth + rdepth + 1, max(lLongPath, rLongPath));
}

Ответ 6

Я думаю, что вы слишком много.

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

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

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

• Самый длинный путь в поддереве, корень которого - n.left_child
• Самый длинный путь в поддереве, корень которого равен n.right_child
• Самый длинный путь, проходящий через node n и не доходящий до родителя n

Ответ 7

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

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

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

Теперь h каждого node 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
• ?? если только n.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 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 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, чтобы заставить этот код работать; однако это решение ужасно неэффективно. Его цель - просто понять расчет.

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

Ответ 8

Ну, ммм, если я правильно понял ваш вопрос, вот мое решение [но в С++ (извините)]:

int h(const Node<T> *root)
{
    if (!root)
        return 0;
    else
        return max(1+h(root->left), 1+h(root->right));
}

void longestPath(const Node<T> *root, int &max)
{
    if (!root)
        return;
    int current = h(root->left) + h(root->right) + 1;
    if (current > max) {
        max = current;
    }
    longestPath(root->left, max);
    longestPath(root->right, max);
}

int longest()
{
    int max = 0;
    longestPath(root, max);
    return max;
}

Ответ 9

Принимая во внимание пример @phimuemue и решение @IVlad, я решил проверить его сам, так вот моя реализация решения @IVlad в python:

def longestPath(graph,start, path=[]):
    nodes = {}
    path=path+[start]
    for node in graph[start]:
        if node not in path:
            deepestNode,maxdepth,maxpath = longestPath(graph,node,path)
            nodes[node] = (deepestNode,maxdepth,maxpath)
    maxdepth = -1
    deepestNode = start
    maxpath = []
    for k,v in nodes.iteritems():
        if v[1] > maxdepth:
            deepestNode = v[0]
            maxdepth = v[1]
            maxpath = v[2]
    return deepestNode,maxdepth +1,maxpath+[start]

if __name__ == '__main__':
    graph = { '1' : ['2','3'],
              '2' : ['1','4','5'],
              '3' : ['1'],
              '4' : ['2','6','7'],
              '5' : ['2','8'],
              '6' : ['4'],
              '7' : ['4','9','a'],
              '8' : ['5','b'],
              '9' : ['7'],
              'a' : ['7'],
              'b' : ['8']
    }
    """
          1
         / \
        2   3
       / \
      4   5
     / \   \
    6   7   8
       / \   \
      9   a   b
    """
    deepestNode,maxdepth,maxpath = longestPath(graph,'1')
    print longestPath(graph, deepestNode)

>>> ('9', 6, ['9', '7', '4', '2', '5', '8', 'b'])