在二叉树中找到最长路径

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

我的问题是：使用深度优先搜索，如何判断我已经找到了最长路径，以便可以将节点添加到我的列表中？

- Mike John

---

听起来像是一份作业/任务。 - Raptor

如果您编写了二叉树类，可以记录其高度和宽度，有时这很有用以确定使用哪种搜索类型。 - Serdalis

你需要定义“路径”。你是指从根到叶子的路径吗？还是指从某个叶子到任何其他叶子的最长路径？这两者有很大的区别。 - Gene

是的，我会给它一个根节点，然后尝试找到最长的路径，这条路径可能不是根节点。它可以从根节点的左边到右边。例如，在前缀为abc的树中，根节点是a，但最长的路径是bac。我传递的根节点只是树，除了保存所有子节点之外没有任何特殊含义。 - Mike John

只要它是最长的路径，就可以。我想让敌人在路径开始的地方生成，即该节点上。 - Mike John

Answer 1

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

- Majid Darabi

---

树的直径是最长的路径！ - Majid Darabi

@MajidDarabi 树中的路径 - 是一个连续的节点序列，只能使用指针（指向左右叶子）遍历，直径不是一条路径！ - vladon

@VladislavYaroslavlev，您能否在树路径的定义中添加一个参考文献吗？（科学论文或书籍）因为基于图中路径的一般定义，我无法得出您的定义。https://en.wikipedia.org/wiki/Path_%28graph_theory%29 - Majid Darabi

Answer 2

请查看以下链接中Niki提供的答案，那是O(n)解决方案。

二叉树的直径 - 更好的设计

- San

Answer 3

我会保留这个答案，以备有需要的人。这是我的c++解决方案。 函数Get_Max_Path()返回一个向量，其中包含最长路径本身，因此您可以得到路径、长度和总和（如果需要）。

vector<int> Max_Path(vector<int>rightpath, vector<int>leftpath)
{
    return (rightpath.size() > leftpath.size()) ? rightpath : leftpath;
}

vector<int> GetPath(node* N, vector<int> v)
{
    v.push_back(N->Data);
    return v;
}
vector<int> Get_Max_Path(node* root)
{
    if (!root) return 
        vector<int>(0);
    return Max_Path(GetPath( root, Get_Max_Path(root->Right)), 
                    GetPath( root, Get_Max_Path(root->Left)) );
}

这里是树形结构

class node
{
public:
    node* Right = NULL;
    node* Left = NULL;
    int Data;
};

class Tree
{
private:
    node* Root = NULL;

public:

    void Insert_Node(int Data)
    {
        node* DataNode = (node*)malloc(sizeof(node));
        DataNode->Data = Data;
        DataNode->Left = DataNode->Right = NULL;

        if (Root == NULL) {
            Root = DataNode;
            return;
        }

        node* tmp_root = Root, * prev = NULL;
        while (tmp_root != NULL)
        {
            prev = tmp_root;
            tmp_root = (tmp_root->Data < Data) ?
                tmp_root->Right :
                tmp_root->Left;
        }
        (prev->Data < Data) ? (prev->Right = DataNode) : (prev->Left = DataNode);
    }

    vector<int> Max_Path(vector<int>rightpath, vector<int>leftpath)
    {
        return (rightpath.size() > leftpath.size()) ? rightpath : leftpath;
    }
    vector<int> Update_Path(node* N, vector<int> v)
    {
        v.push_back(N->Data);
        return v;
    }
    vector<int> Get_Max_length_Path(node* root)
    {
        if (!root) return
            vector<int>(0);
        return Max_Path(
            Update_Path(root, Get_Max_length_Path(root->Right)),
            Update_Path(root, Get_Max_length_Path(root->Left)));
    }

    vector<int> Get_Max_length_Path()
    {
        return Get_Max_length_Path(Root);
    }
};

这是驱动代码

int main()
{
    Tree T;

    int nodes[] = { 11, 6, 8, 19, 4, 13, 5, 17, 43, 49, 16, 31, 32};
    int length = sizeof(nodes) / sizeof(nodes[0]);

    for (size_t i = 0; i < length; i++)
        T.Insert_Node(nodes[i]);

    int sum = 0;

    vector<int> path = T.Get_Max_length_Path();
    cout << "The path length is : " << path.size() <<endl;
    cout << "The path from the leaf to the root is : ";
    for (int i = 0; i < path.size(); i++)
    {
        cout << path[i] << " ";
        sum += path[i] ;
    }
    cout << endl;
    cout << "the path sum is :" << sum << endl;
    return 0;
}

测试用例

BST示例

输出

The path length is : 5 The path from the leaf to the root is : 16 17
13 19 11 the path sum is :76

- Hassan Essam