当前位置：首页 > news >正文

LeetCode题练习与总结：完全二叉树的节点个数--222

news 2025/6/12 22:56:09

一、题目描述

给你一棵 完全二叉树 的根节点 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
题目数据保证输入的树是 完全二叉树

二、解题思路

对于完全二叉树，我们可以使用递归的方法来计算节点的个数。递归的基本思想是，一个节点的节点数等于其左子树的节点数加上其右子树的节点数，再加上自身（1）。
从根节点开始，递归地对每个节点的左右子树进行计算，直到叶子节点（没有子节点的节点）。
在递归过程中，如果遇到空节点（null），则返回0，因为空节点不计算在内。
最终，递归的结果就是整个完全二叉树的节点总数。

三、具体代码

class Solution {public int countNodes(TreeNode root) {// 如果当前节点为空，返回0if (root == null) {return 0;}// 递归计算左子树的节点数int leftCount = countNodes(root.left);// 递归计算右子树的节点数int rightCount = countNodes(root.right);// 当前节点的节点数等于左子树节点数加上右子树节点数，再加上当前节点本身return leftCount + rightCount + 1;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

该算法需要访问树中的每一个节点，因此它的时间复杂度取决于树中节点的数量。
在最坏的情况下，完全二叉树可能退化成一个链表，此时算法需要遍历整个树，时间复杂度为 O(n)，其中 n 是树中节点的数量。
在平均情况下，由于完全二叉树的特性，算法的时间复杂度依然是 O(n)，因为算法需要访问每个节点。

因此，该算法的时间复杂度是 O(n)，其中 n 是完全二叉树中的节点数量。

2. 空间复杂度

空间复杂度主要取决于递归调用的栈深度。
在最坏的情况下，树可能是一个完全平衡的二叉树，此时递归的深度为 log(n)，其中 n 是树中节点的数量。
因此，递归栈的空间复杂度为 O(log(n))。

综上所述，该算法的空间复杂度是 O(log(n))，其中 n 是完全二叉树中的节点数量。

五、总结知识点

递归（Recursion）：代码通过递归的方式计算完全二叉树的节点数。递归是一种常见的算法设计技巧，它允许函数调用自身来解决问题。
二叉树（Binary Tree）：代码操作的是二叉树数据结构。二叉树是一种树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。
完全二叉树（Complete Binary Tree）：题目中特别指出所操作的树是完全二叉树，这意味着树中的每一层（除了最后一层）都被完全填满，并且最后一层的节点都靠左排列。
基础条件（Base Case）：在递归函数中，if (root == null) 是基础条件，它定义了递归的停止条件。当遇到空节点时，递归结束，返回0。
递归调用（Recursive Call）：countNodes(root.left) 和 countNodes(root.right) 是递归调用，它们分别计算左子树和右子树的节点数。
递归合并（Recursive Combination）：在递归的每一步，节点数通过 leftCount + rightCount + 1 来合并。这体现了递归解决问题的分而治之策略。
整型数据类型（Integer Data Type）：代码中使用了 int 数据类型来存储节点数，它是 Java 中的基本数据类型之一，用于表示整数。
条件语句（Conditional Statement）：使用了 if 语句来检查节点是否为空，这是一种控制流语句，用于根据条件执行不同的代码路径。