java 2个节点之间的最长路径

Longest path between 2 Nodes

提问by George Kagan

Calculate the longest path between two nodes.
The path is in an arch.
Signature of method is:

计算两个节点之间的最长路径。
路径是在一个拱形。
方法的签名是：

public static int longestPath(Node n)

In the example binary tree below, it is 4(going thru 2-3-13-5-2).

在下面的示例二叉树中，它是4（通过 2-3-13-5-2）。

This is what I have right now and for the given tree it just returns 0.

这就是我现在所拥有的，对于给定的树，它只返回 0。

public static int longestPath(Node n) {
    if (n != null) {
        longestPath(n, 0);
    }
    return 0;
}
private static int longestPath(Node n, int prevNodePath) {

    if (n != null && n.getLeftSon() != null && n.getRightSon() != null) {
        int currNodePath = countLeftNodes(n.getLeftSon()) + countRightNodes(n.getRightSon());
        int leftLongestPath = countLeftNodes(n.getLeftSon().getLeftSon()) + countRightNodes(n.getLeftSon().getRightSon());
        int rightLongestPath = countLeftNodes(n.getRightSon().getLeftSon()) + countRightNodes(n.getRightSon().getRightSon());

        int longestPath = currNodePath > leftLongestPath ? currNodePath : leftLongestPath;
        longestPath = longestPath > rightLongestPath ? longestPath : rightLongestPath;

        longestPath(n.getLeftSon(), longestPath);
        longestPath(n.getRightSon(), longestPath);

        return longestPath > prevNodePath ? longestPath : prevNodePath;
    }
    return 0;
}
private static int countLeftNodes(Node n) {
    if (n != null) {
        return 1+ countLeftNodes(n.getLeftSon());
    }
    return 0;
}
private static int countRightNodes(Node n) {
    if (n != null) {
        return 1+ countRightNodes(n.getRightSon());
    }
    return 0;
}

I understand that I'm missing a key concept somewhere... My brain goes crazy when I try tracking the flow of execution...
Am I right by saying that by finding the longest path among the root, its left & right nodes and then recurse on its left & right nodes passing them the longest path from previous method invocation and finally (when?) return the longest path, I'm not certain as to how you go about returning it...

我知道我在某处遗漏了一个关键概念......当我尝试跟踪执行流程时，我的大脑发疯了......
我说通过在根、其左右节点和它的左右节点之间找到最长的路径，我说得对吗？然后在它的左右节点上递归，传递上一个方法调用中最长的路径，最后（什么时候？）返回最长的路径，我不确定你如何返回它......

回答by phimuemue

Maybe it is just as simple:

也许它也很简单：

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

Its more complicated than one might think at first sight. Consider the following tree:

它比第一眼想象的要复杂。考虑以下树：

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

In this case, the root node is not even in the longest path (a-7-4-2-5-8-b).

在这种情况下，根节点甚至不在最长路径 ( a-7-4-2-5-8-b) 中。

So, what you must do is the following: For each node nyou must compute the following:

因此，您必须执行以下操作：对于每个节点，n您必须计算以下内容：

• compute longest path in left subtree starting with the root of the left subtree (called L)
• compute longest path in right subtree starting with the root of the right subtree (called R)
• compute the longest path in left subtree (not necessarily starting with the root of the left subtree) (called l)
• compute the longest path in right subtree (not necessarily starting with the root of the right subtree) (called r)

• 从左子树的根开始计算左子树中的最长路径（称为L）
• 从右子树的根开始计算右子树中的最长路径（称为R）
• 计算左子树中最长的路径（不一定从左子树的根开始）（称为l）
• 计算右子树中最长的路径（不一定从右子树的根开始）（称为r）

Then, decide, which combination maximizes path length:

然后，决定哪种组合使路径长度最大化：

• L+R+2, i.e. going from a subpath in left subtree to current node and from current node through a subpath in right subtree
• l, i.e. just take the left subtree and exclude the current node (and thus right subtree) from path
• r, i.e. just take the right subtree and exclude the current node (and thus left subtree) from path

• L+R+2, 即从左子树中的子路径到当前节点以及从当前节点通过右子树中的子路径
• l，即只取左子树并从路径中排除当前节点（以及右子树）
• r, 即只取右子树并从路径中排除当前节点（以及左子树）

So I would do a little hack and for every node not return just a single int, but a triple of integers containing (L+R+2, l, r). The caller then must decide what to do with this result according to the above rules.

所以我会做一些小技巧，对于每个节点，不只返回一个int，而是返回包含(L+R+2, l, r). 然后调用者必须根据上述规则决定如何处理这个结果。

回答by IVlad

A correct algorithm is:

正确的算法是：

1. Run DFS from any node to find the farthest leaf node. Label that node T.
2. Run another DFS to find the farthest node from T.
3. The path you found in step 2 is the longest path in the tree.

1. 从任何节点运行 DFS 以查找最远的叶节点。标记该节点 T。
2. 运行另一个 DFS 以查找距离 T 最远的节点。
3. 您在第 2 步中找到的路径是树中最长的路径。

This algorithm will definitely work, and you're not limited to just binary trees either. I'm not sure about your algorithm:

该算法肯定会起作用，而且您也不仅限于二叉树。我不确定你的算法：

Am I right by saying that by finding the longest path among the root, its left & right nodes and then recurse on its left & right nodes passing them the longest path from previous method invocation and finally (when???) return the longest path, I'm not certain as to how you go about returning it...

我说通过找到根中最长的路径，它的左右节点，然后在它的左右节点上递归传递上一个方法调用中最长的路径，最后（当？？？）返回最长的路径，我说的对吗？ ，我不确定你是如何退货的......

because I don't understand what exactly you're describing. Can you work it by hand on an example or try to explain it better? That way you might get better help understanding if it's correct or not.

因为我不明白你在描述什么。你能在一个例子上手工操作它还是尝试更好地解释它？这样你可能会得到更好的帮助来理解它是否正确。

You seem to be attempting a recursive implementation of basically the same thing just simplified for binary trees. Your code seems rather complicated for this problem however. Check the discussion herefor a simpler implementation.

您似乎正在尝试递归实现基本相同的东西，只是针对二叉树进行了简化。但是，您的代码对于这个问题似乎相当复杂。查看此处的讨论以获得更简单的实现。

回答by Shawn

Here is my recursive solution in C++:

这是我在 C++ 中的递归解决方案：

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) );
}

回答by James Yu

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 };
}

回答by bicepjai

Simple Implementation:

简单的实现：

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));
}

回答by Francisco Valdez

Taking into account @phimuemue example and @IVlad solution, I decided to check it out myself, so here is my implementation of @IVlad solution in python:

考虑到@phimuemue 示例和@IVlad 解决方案，我决定自己检查一下，所以这是我在python 中实现@IVlad 解决方案：

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'])

回答by Maciej Hehl

I think You are overcomplicating things.

我认为你把事情复杂化了。

Think about the longest path that goes through the node n and doesn't go up to the parent of n. What is the relationship between the length of that path and the heights of both subtries connected to n?

考虑通过节点 n 并且不到达 n 的父节点的最长路径。该路径的长度与连接到 n 的两个子树的高度之间有什么关系？

After figuring that out, check the tree recursively reasoning like this:

弄清楚之后，像这样递归地检查树：

The longest path for a subtree with the root n is the longest path of the following three:

具有根 n 的子树的最长路径是以下三个中最长的路径：

1. The longest path in the subtree, whose root is n.left_child
2. The longest path in the subtree, whose root is n.right_child
3. The longest path, that goes through the node n and doesn't go up to the parent of n

1. 子树中最长的路径，其根为 n.left_child
2. 子树中最长的路径，其根为 n.right_child
3. 最长的路径，通过节点 n 并且不会到达 n 的父节点

回答by Daniel Trebbien

What if, for each node n, your goal was to compute these two numbers:

如果对于每个节点n，您的目标是计算这两个数字，该怎么办：

• f(n): The length of the longest path in the tree rooted at n
• h(n): The height of the tree that is rooted at n.

• f( n)：树中最长路径的长度n
• h( n)：以 为根的树的高度n。

For each terminal node (nodes having nullleft and right nodes), it is obvious that f and h are both 0.

对于每个终端节点（具有null左右节点的节点），很明显 f 和 h 都是 0。

Now, the h of each node nis:

现在，每个节点的 hn是：

• 0 if n.leftand n.rightare both null
• 1 + h(n.left) if only n.leftis non-null
• 1 + h(n.right) if only n.rightis non-null
• 1 + max(h(n.left), h(n.right)) if both n.leftand n.rightare non-null

• 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

And f(n) is:

而 f( n) 是：

• 0 if n.leftand n.rightare both null
• max(f(n.left), h(n)) if only n.leftis non-null
• ?? if only n.rightis non-null
• ?? if both n.leftand n.rightare non-null

• 0 如果n.left和n.right都是null
• max(f( n.left), h( n)) 如果仅n.left是非null
• ?? 如果只是n.right非null
• ?? 如果两个n.left和n.right是非null

(You need to figure out what replaces the two "??" placeholders. There are choices that make this strategy work. I have tested it personally.)

（你需要弄清楚是什么取代了两个“??”占位符。有一些选择可以使这个策略起作用。我亲自测试过。）

Then, longestPath(Node n)is just f(n):

那么，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.
    }
}

You should be able to write recursive implementations of f and h to make this code work; however, this solution is horribly inefficient. Its purpose is just to understand the calculation.

您应该能够编写 f 和 h 的递归实现来使此代码工作；然而，这种解决方案的效率非常低。它的目的只是为了理解计算。

To improve the efficiency, you could use memoizationor convert this to a non-recursive calculation that uses stack(s).

为了提高效率，您可以使用记忆化或将其转换为使用堆栈的非递归计算。

回答by Daniel Trebbien

Well, umm if I've understood your question correctly, here is my solution [but in C++(I'm sorry)]:

嗯，嗯，如果我正确理解了你的问题，这是我的解决方案 [但在 C++ 中（对不起）]：

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;
}