4

我想在二叉树中找到最长的路径。我打算将它们添加到列表中，这样我就可以告诉我的敌人角色在简单模式下走很长的路。

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 找到了最长的路径，以便我可以将节点添加到我的列表中？

4

3 回答 3

8

一棵树中最长的路径，称为“直径”。你可以在这里看到算法的实现：http ://www.geeksforgeeks.org/diameter-of-a-binary-tree/

于 2013-03-19T05:28:21.323 回答
2

检查 Niki 在以下链接中给出的答案。这是 O(n) 解决方案

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

于 2013-11-17T15:46:35.747 回答
0

如果有人需要，我会留下这个答案。这是我在 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 样本 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
于 2020-02-16T08:05:07.190 回答