二叉树的最长路径问题|PTA|C++

    template <typename E>
    int LongestPathInBinaryTree(BinNode<E>* root, int& 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;
    
    }
    
    /* 请在这里填写答案 */

    7
    9 7 5 19 11 13 21

    5

    int res=0;
    template<typename E>
    int getHeight(BinNode<E>* root){
    if(!root)
        return 0;
    int left=getHeight(root->left());
    int right=getHeight(root->right());
    
    res=max(res,left+right);
    return 1+max(left,right);
    }
    template<typename E>
    int LongestPathInBinaryTree(BinNode<E>* root, int& max_dist){
    if(!root)
        return 0;
    getHeight(root);
    max_dist=res;
    return res;