首页 > 程序开发 > 综合编程 > 其他综合 > 正文
二叉树的直径
2017-03-20 09:35:19       个评论      
收藏    我要投稿

二叉树的直径:二叉树中从一个结点到另一个节点最长的路径,叫做二叉树的直径 采用分治和递归的,根节点为root的二叉树的直径 = max(root-left的直径,root->right的直径,root->left的最大深度+root->right的最大深度+1)

代码

// 求二叉树的直径
int diameterOfBinaryTree(TreeNode* root) 
{
    if(root == nullptr)
        return 0;
    int d_l=diameterOfBinaryTree(root->left);
    int d_r = diameterOfBinaryTree(root->right);
    int height_l=getHeight(root->left);
    int height_r=getHeight(root->right);

    int tmp1=d_l > d_r ? d_l :d_r;
    int tmp2=height_l+height_r+1;
    return tmp1>tmp2 ? tmp1 :tmp2; 
}
// 获得二叉树的最大深度
int Solution::getHeight(TreeNode* root)
{
    if(root == nullptr)
        return 0;
    int h_l=getHeight(root->left);
    int h_r=getHeight(root->right);
    return ((h_l > h_r) ? h_l :h_r)+1;
}
点击复制链接 与好友分享!回本站首页
上一篇:eclipse中jsp文件修改浏览器没有同步
下一篇:二分查找算法
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站