如果把二叉树看着无向图，可以求出任意两个节点间的路径长度，与路径中经过的边数量相等。这里的路径指的是简单路径，即同一个节点不会在路径上出现两次以上。求二叉树中所有节点之间的路径长度的最大值。 函数接口定义： template <typename E> int LongestPathInBinaryTree(BinNode<E>* root, int& max_dist); root指向二叉树的根（初始值），max_dist用来记录二叉树的最长路径长度。 裁判测试程序样例： #include <iostream> template <typename E> class BinNode{ public: virtual ~BinNode() {} virtual BinNode* left() const = 0; //返回左子树的根位置 virtual BinNode* right() const = 0; //返回右子树的根位置 virtual bool isLeaf() = 0; }; //二叉树节点 template <typename E> BinNode<E>* constructBinTree(const int N); //生成N个节点的二叉树，返回根位置（过程省略） template <typename E> int LongestPathInBinaryTree(BinNode<E>* root, int& max_dist); int main() { int N; //节点数量 ... BinNode<int> root = constructBinTree<int>(N); int max_dist = 0; //最长路径长度的初始值 LongestPathInBinaryTree<int>(root, max_dist); //寻找最长路径 cout << max_dist << endl; //输出最长路径的长度 ... return 0; } /* 请在这里填写答案 */

下面是一种基于递归的求解方式：

template <typename E>
int distance(BinNode<E> *node, int &max_dist) {
    if (!node) {
        return -1;
    }
    int left = distance(node->left(), max_dist) + 1; // 左子树中的最长路径长度
    int right = distance(node->right(), max_dist) + 1; // 右子树中的最长路径长度
    max_dist = std::max(max_dist, left + right); // 更新最长路径长度
    return std::max(left, right); // 返回以当前节点为根的子树中的最长路径长度
}

template <typename E>
int LongestPathInBinaryTree(BinNode<E> *root, int &max_dist)
{
    distance(root, max_dist);
    return max_dist;
}

在这个递归函数中，我们首先判断当前节点是否为空。如果为空，则返回 -1。对于每个非空节点，我们分别计算其左子树和右子树中的最长路径长度（通过递归调用 distance 函数实现），然后将左右路径长度相加，得到以当前节点为根的路径长度。同时，我们还需要更新最长路径长度 max_dist，即当前节点的左右路径长度之和。最后，函数返回以当前节点为根的子树中的最长路径长度，即左右路径长度中的最大值加一。

在 main 函数中，我们调用 LongestPathInBinaryTree 函数，并将其返回值作为最终结果输出即可。