找到二叉树中最长的路径

Question

我想找到二叉树中最长的路径.我计划将它们添加到列表中,这样我就能告诉我的敌人角色在简易模式上走很长的路.

private static <T> ArrayList<T> depthFirstSearch(BinaryNode<T> node)
{
    if(node != null)
    {
        Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();

        stack.push(node);

        while(!stack.isEmpty())
        {
            BinaryNode<T> currentNode = stack.pop();



            if(currentNode.right != null)
                stack.push(currentNode.right);

            // We want to visit left child first, so push left node last.
            if(currentNode.left != null) 
                stack.push(currentNode.left);
        }
    }
}

我写了那段代码,但这是一团糟.我正在尝试使用DFS找到最长的路径.有什么建议？

编辑:我确实有树的高度,我可以使用它.

public static <T> int height(BinaryNode<T> t)
{
    if (t == null)
        return -1;

    else 
        return 1 + Math.max(height(t.left), height(t.right));
}

我的问题是:我何时知道我找到了使用DFS的最长路径,以便我可以将节点添加到我的列表中？

Answer 1

树中最长的路径称为"直径".您可以在此处查看算法的实现:http://www.geeksforgeeks.org/diameter-of-a-binary-tree/