大数据平台 Nmap 百度搜索优化 variables testing vue官方下载 vue响应式 bootstrap后台管理 传智播客python jq绑定click事件 matlab读入图片 pyhton中异常和模块 python中sort函数 python迭代 python中import用法 java包 java类型 ie模拟器 嵌入式linux驱动程序设计从入门到精通 python入门经典 迅雷免费会员号共享 考试练习系统 getelementbyid skycc组合营销软件 自动答题软件 mac画图工具 jsp源码 jquery下载 dnf传说 文件批量更名 打印机怎么打印照片 wps苹果mac版 pr脱机文件怎么恢复 mysql闪退 人马上单天赋 cdr填充颜色 热键助手 baidupan dwg看图软件 苹果手机怎么双开微信
当前位置: 首页 > 学习教程  > 编程语言

letecode 编程学习(16)

2020/11/24 9:13:09 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目 给出一个完全二叉树,求出该树的节点个数。 说明: 完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位…

题目

给出一个完全二叉树,求出该树的节点个数。

说明:

完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

示例:

输入: 
    1
   / \
  2   3
 / \  /
4  5 6

输出: 6

解题思路

  • 直接采用深度或者广度遍历获取所有的节点进行统计,这样时间复杂度O(n)
  • 根据完全二叉树的特点(右边的肯定是满二叉树),这样优化时间可以做到O(log(n)*log(n))

代码

这里给出了第一种思路的代码

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == NULL)
        {
            return 0;
        }

        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

 


本文链接: http://www.dtmao.cc/news_show_400006.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?