找到一个二叉树的最长路径 [英] Finding the Longest Path in a Binary Tree

问题描述

我想找到一个二叉树的最长路径。我打算将它们添加到列表中，这样，我可以告诉我的敌人角色采取简易模式的漫长道路。

I want to find the longest path in a Binary Tree. I plan to add them to a list, that way I can tell my enemy character to take the long path on easy mode.

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

我写了code，但它是一个烂摊子。我试图使用DFS找采取的最长路径。有什么建议？

I have written that code, but it is a mess. I am trying to use DFS to find the longest path to take. Any suggestions?

编辑：我有树的高度，我可以用这个让

I do have the height of the tree, I can get it using this.

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这样我就可以将节点添加到我的名单最长的路径

推荐答案

在树中的最长的路径，被称为直径。你可以看到这里的算法的实现： HTTP：//www.geeksforgeeks。组织/直径的一二进制树/

The longest path in a tree, is called "diameter". You can see the implementation of the algorithm here: http://www.geeksforgeeks.org/diameter-of-a-binary-tree/

这篇关于找到一个二叉树的最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！