侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

【递归, 二叉树】完全二叉树的节点个数

GabrielxD
2022-10-20 / 0 评论 / 0 点赞 / 283 阅读 / 300 字
温馨提示:
本文最后更新于 2022-11-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

222. 完全二叉树的节点个数


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

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

示例 1:

输入:root = [1,2,3,4,5,6]
输出:6

示例 2:

输入:root = []
输出:0

示例 3:

输入:root = [1]
输出:1

提示:

  • 树中节点的数目范围是[0, 5 * 10^4]
  • 0 <= Node.val <= 5 * 10^4
  • 题目数据保证输入的树是 完全二叉树

**进阶:**遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗?

解题

方法一:递归

思路

跟简单的递归,见代码。

代码

class Solution {
    public int countNodes(TreeNode root) {
        return root == null ? 0 : countNodes(root.left) + countNodes(root.right) + 1;
    }
}
0

评论区