题目地址(222. 完全二叉树的节点个数)

https://leetcode-cn.com/problems/count-complete-tree-nodes/

题目描述

  1. 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
  3. 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
  7. 示例 1：
  9. 输入：root = [1,2,3,4,5,6]
  10. 输出：6
  13. 示例 2：
  15. 输入：root = []
  16. 输出：0
  19. 示例 3：
  21. 输入：root = [1]
  22. 输出：1
  27. 提示：
  29. 树中节点的数目范围是[0, 5 * 104]
  30. 0 <= Node.val <= 5 * 104
  31. 题目数据保证输入的树是 完全二叉树
  35. 进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

前置知识


公司

  • 暂无

思路

使用递归

首先确定好循环的返回值和参数
返回值是int 最后要返回完全二叉树的节点数 参数就是 treeNode

然后确定终止条件
终止条件为节点等于空 返回0

然后就是每次递归的逻辑判断
递归的调用左子树 再递归的调用右子树 然后将左右子树的返回值相加再加上根节点的1

使用迭代

就是使用层序遍历 然后每次遍历到一个节点就使计数器加1

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public int countNodes(TreeNode root) {
  19.             if (root == null) {
  20.                 return 0;
  21.             }
  22.             int left = countNodes(root.left);
  23.             int right = countNodes(root.right);
  24.             return left + right + 1;
  25.         }
  26.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：222. 完全二叉树的节点个数 - 图1#card=math&code=O%28n%29&id=cCl40)
  • 空间复杂度：222. 完全二叉树的节点个数 - 图2#card=math&code=O%28n%29&id=xER7m)