代码之家 › 专栏 › 技术社区 › George Kagan

两个节点之间的最长路径

binary-tree recursion algorithm java

George Kagan · 技术社区 · 14 年前

这条路呈拱形。

public static int longestPath(Node n)

在下面的二叉树示例中,它是 4 (通过2-3-13-5-2)。

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

我说的对吗?通过在根中找到最长的路径,它的左边&右节点,然后在其左侧递归;右节点向它们传递上一次方法调用的最长路径,最后(何时?)返回最长路径,我不确定如何返回它。。。

9 回复 | 直到 8 年前

phimuemue 14 年前

也许就这么简单:

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

它比人们乍一看所想的要复杂得多。考虑以下树:

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

因此,您必须执行以下操作:对于每个节点 n

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

然后,决定哪个组合使路径长度最大化:

L+R+2
我 ,即只取左子树,并从路径中排除当前节点(从而右子树)
r ,即只取右子树,并从路径中排除当前节点(以及左子树)

int ,但包含 (L+R+2, l, r) . 然后,调用者必须根据上述规则决定如何处理这个结果。

IVlad 14 年前

正确的算法是:

从任何节点运行DFS以查找最远的叶节点。标记节点T。
在步骤2中找到的路径是树中最长的路径。

我说的对吗?通过在根中找到最长的路径,它的左边&右节点,然后在其左侧递归;右节点向它们传递上一次方法调用的最长路径,最后(何时?)返回最长路径,我不确定如何返回它。。。

因为我不明白你到底在说什么。你能用手举一个例子吗?还是试着更好地解释?这样你就可以更好地理解它是否正确。

您似乎在尝试一个递归实现,基本上与刚才为二叉树简化的实现相同。但是,对于这个问题,您的代码似乎相当复杂。检查讨论 here 更简单的实现。

James Yu 12 年前

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

bicepjai 12 年前

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

andrewsi Laxman Battini 12 年前

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

Paco Valdez 12 年前

考虑到@phimuemue示例和@IVlad solution,我决定亲自检查一下,下面是我在python中对@IVlad solution的实现:

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

Maciej Hehl 14 年前

我觉得你把事情搞得太复杂了。

弄清楚之后,检查树递归推理如下:

子树中最长的路径,其根是n.right\u child
最长的路径,它穿过节点n而不到达节点n的父节点

Daniel Trebbien 14 年前

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

f级( ):树中最长路径的长度 n
n ):根所在树的高度 .

对于每个终端节点(具有 null

现在,每个节点的h n

0如果 n.left 和 n.right 两者都是 无效的
1+小时( )但愿如此是非- 无效的
n、是吗 )但愿如此是非-
1+最大值(h( n、左 ),小时( n、是吗 和

n )是:

0如果 n、左 和两者都是
最大值(f( n、左 ),小时( n n、左 是非- 无效的
?? 要是…就好了 无效的
n、左 和 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.
    }
}

为了提高效率,您可以使用 memoization 或者将其转换为使用堆栈的非递归计算。

user551761 user551761 14 年前

嗯,如果我已经正确地理解了你的问题,这里是我的解决方案[但是在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;
}