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

函数接口

template 
int LongestPathInBinaryTree(BinNode* root, int& max_dist);

裁判测试程序样例

#include 

template 
class BinNode{
    public:
        virtual ~BinNode() {}
        virtual BinNode* left() const = 0; //返回左子树的根位置
        virtual BinNode* right() const = 0; //返回右子树的根位置
        virtual bool isLeaf() = 0;
}; //二叉树节点

template 
BinNode* constructBinTree(const int N);
//生成N个节点的二叉树，返回根位置（过程省略）

template 
int LongestPathInBinaryTree(BinNode* root, int& max_dist);

int main()
{
  int N; //节点数量
    ...
  BinNode root = constructBinTree(N);

  int max_dist = 0;    //最长路径长度的初始值
  LongestPathInBinaryTree(root, max_dist);  //寻找最长路径
  cout << max_dist << endl;      //输出最长路径的长度
   ...
  return 0;

}

输入样例：

7
9 7 5 19 11 13 21

输出样例

5

int res=0;
template
int getHeight(BinNode* 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
int LongestPathInBinaryTree(BinNode* root, int& max_dist){
    if(!root)
        return 0;
    getHeight(root);
    max_dist=res;
    return res;

22 二叉树的最长的路径长度和最大路径和