引言

大家好啊，我是前端拿破轮😁。

跟着卡哥学算法有一段时间了，通过代码随想录的学习，受益匪浅，首先向卡哥致敬🫡。

但是在学习过程中我也发现了一些问题，很多当时理解了并且AC的题目过一段时间就又忘记了，或者不能完美的写出来。根据费曼学习法，光有输入的知识掌握的是不够牢靠的，所以我决定按照代码随想录的顺序，输出自己的刷题总结和思考。同时，由于以前学习过程使用的是JavaScript,而在2025年的今天，TypeScript几乎成了必备项，所以本专题内容也将使用TypeScript，来巩固自己的TypeScript语言能力。

题目信息

完全二叉树的节点个数

leetcode题目链接

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

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

题目分析

我们直接给出普通二叉树的求解方式。

递归方式

还是按照递归三部曲

  1. 确定递归函数的参数和返回值以及他们的意义

我们来看下题目提供的函数能否满足条件

1
2
function countNodes(root: TreeNode | null): number {
};

这个函数有一个参数，是传入的根节点。返回值是一个数字，表示整棵树中的节点数量。那么原始问题和子问题之间有没有相同的性质呢？当然，我们只需要求出左右子树的节点数量，再加上根节点自身，就可以得到整棵树的节点数了。

所以题目的函数是可以直接用作递归函数的。

  1. 确定终止条件

当前根节点为null时终止，返回0即可。

  1. 确定单层递归逻辑

用技巧，我们只考虑最外层的递归，就是根节点那里。调用递归函数自身求得左右子树的节点数后。将两者相加再加上根节点自己就是整个树的节点数量了。

层序遍历方式

层序遍历要利用队列来进行。首先初始化节点数为0，然后按照正常的层序遍历方式，将根节点入队。每次从队头出队元素时，就让节点数+1，最后返回统计结果即可。

题解

递归方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function countNodes(root: TreeNode | null): number {
  // 确定终止条件
  if (!root) return 0;

  // 确定单层递归逻辑
  return 1 + countNodes(root.left) + countNodes(root.right);
}

时间复杂度：$O(n)$

空间复杂度：$O(h)$, h是树的高度

层序遍历方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function countNodes(root: TreeNode | null): number {
  // 确定终止条件
  if (!root) return 0;

  // 初始化节点数
  let count = 0;

  // 辅助队列
  const queue: TreeNode[] = [];

  // 根节点入队
  queue.push(root);

  // 当队列非空时，开始遍历
  while (queue.length) {
    // 由于不需要存储各层节点，所以没必要保存队列长度
    // 元素出队
    const node = queue.shift();
    
    // 计数+1
    count++;

    // 如果有左右孩子则入队
    node.left && queue.push(node.left);
    node.right && queue.push(node.right);
  }
  return count;
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

总结

本题考察二叉树节点数量的计算方式，用DFS和BFS都可以。在使用DFS时，要注意使用递归三部曲，每一步都得自己给自己讲清楚。在使用BFS时，没有必要进行节点存储，只需要计数即可，所以也没有必要像层序遍历原题那样保存每层的节点数。

感兴趣的同学可以订阅本专栏刷爆leetcode，持续更新。

好了，这篇文章就到这里啦，如果对您有所帮助，欢迎点赞,收藏,分享👍👍👍。您的认可是我更新的最大动力。由于笔者水平有限，难免有疏漏不足之处，欢迎各位大佬评论区指正。

往期推荐✨✨✨

我是前端拿破轮，关注我，一起学习前端知识，我们下期见！