两个节点之间的最长路径

Question

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

public static int longestPath(Node n)

在下面的示例二叉树中，路径是通过2-3-13-5-2得到的，其中节点4位于路径上。

这是我现在拥有的代码，但对于给定的树它只返回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;
}

我明白我在某个关键概念上有所缺失... 当我尝试追踪执行流程时，我的大脑变得混乱起来...
我是否正确地说，通过找到根节点、它的左右节点之间的最长路径，然后在左右节点上递归并传递前一个方法调用中的最长路径，最后（何时？）返回最长路径，但我不确定如何返回它...

- George Kagan

---

当二叉树本质上是一个链表时，你如何处理这种情况？例如，2-3-13（13是根，3在13的左侧，2在3的左侧）。结果应该是2吗？ - Daniel Trebbien

Answer 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

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

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

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

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

• L+R+2，即从左子树中的子路径到当前节点，再从当前节点通过右子树中的子路径移动
• l，即只考虑左子树并将当前节点（因此也是右子树）从路径中排除
• r，即只考虑右子树并将当前节点（因此也是左子树）从路径中排除

因此，我会进行一些小技巧，在每个节点上不仅返回单个int，而是返回包含(L+R+2，l，r)的三个整数的三元组。然后，调用者必须根据上述规则决定如何处理此结果。

- phimuemue

---

谢谢，但我尝试过了，它只返回零。 至于我忘记添加返回语句，我已经添加了它并且确实返回了4，但它只考虑了从根节点延伸的弧...其他比它更长的弧被简单地忽略了。 - George Kagan

实际上，最长的路径是6（例如：a-7-4-2-5-8-b）。虽然这是一个很好的例子。 - Daniel Trebbien

@Daniel 嗯，我理解的方式是路径的形状像一个拱形（倒过来的V）。 - George Kagan

@timeNomad：你可能需要向你的教练请求澄清。对我来说，9-7-4-2-5-8-b仍然是“一个拱形”。另请参阅：http://en.wikipedia.org/wiki/Path_（graph_theory） - Daniel Trebbien

为什么我们需要 l 和 r？我无法想到一个角落案例，其中 L+R+2 不能解决问题。 - user1071840

还有，为什么是 L+R+2？不应该是 L+R+1 吗？对于节点 2，L 是 3（4-7-a/9），R 是 3（5-8-b），因此长度将为 3+3+1[根节点]？ - user1071840

Answer 2

一个正确的算法是：

1. 从任何一个节点开始运行DFS，找到最远的叶子节点。标记该节点为T。
2. 运行另一个DFS，找到距离T最远的节点。
3. 你在步骤2中找到的路径就是树中最长的路径。

这个算法肯定有效，而且你不仅限于二叉树。我不确定你的算法:

我说得对吗？通过在根节点、它的左右节点中找到最长的路径，然后递归地在它的左右节点上运行，传递它们从前一次方法调用中获得的最长路径，最后（何时？）返回最长路径，但我不确定你如何返回它...

因为我不明白你具体描述的是什么。你能手动在一个例子上演示一下吗或者更好地解释一下吗？这样你可能会得到更好的帮助，以理解它是否正确。

你似乎正在尝试一个递归实现，基本上是为了二叉树简化的相同问题。然而，对于这个问题来说，你的代码似乎过于复杂了。在这里检查讨论this，以获得更简单的实现。

- IVlad

---

关于不仅限于二叉树的问题，请查看：http://en.wikipedia.org/wiki/Longest_path_problem该网页指出，该问题（至少对于任意图形）是NP完全的。 - phimuemue

@phimuemue - 是的，我的意思是只要这个图仍然是一棵树。 - IVlad

+1：这个程序可以正确地找到无向树中的最长路径（我想在树的情况下也是直径）。 - Aryabhatta

1. 找到一个循环。
2. 进入它。
3. ...
4. 获利！

- badp

1. 在树中找到一个循环。
2. 向新手图论者出售带有循环的惊人树。
3. 获利。

- Aryabhatta

Answer 3

简单实现：

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

- bicepjai

---

这将是O(n^2)。应该有一个更好的O(n)解决方案。 - Dejell

Answer 4

考虑到@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'])

- Paco Valdez

Answer 5

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

- James Yu

Answer 6

这是我在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) );
}

- Shawn

Answer 7

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

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

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

现在，每个节点 n 的 h 是：

• 如果 n.left 和 n.right 都是 null，则为 0
• 如果只有 n.left 不是 null，则为 1 + h(n.left)
• 如果只有 n.right 不是 null，则为 1 + h(n.right)
• 如果 n.left 和 n.right 都不是 null，则为 1 + max(h(n.left), h(n.right))

而 f(n) 是：

• 如果 n.left 和 n.right 都为 null，则返回 0
• 如果只有 n.left 不为 null，则返回 max(f(n.left), h(n))
• 如果只有 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'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 来使这段代码工作; 然而，这个解决方案非常低效。它的目的只是为了理解计算过程。

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

- Daniel Trebbien

Answer 8

嗯，如果我正确理解了你的问题，这是我的解决方案[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;
}

- user551761

Answer 9

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

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

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

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

1. 子树n.left_child中的最长路径
2. 子树n.right_child中的最长路径
3. 通过节点n且不上到n的父节点的最长路径

- Maciej Hehl