222. 完全二叉树的节点个数
LeetCode题目要求
给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。
完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^(h) 个节点。
示例
![图](/i/l/?n=23&i=blog/458364/202301/458364-20230122203723324-515282602.png)
输入:root = [1,2,3,4,5,6]
输出:6
解题思路
- 一种方法是直接计算节点个数,不管它是什么树
- 根据完全二叉树的特点来计算节点个数,第一种情况是满二叉树,那么只要知道深度,就可以根据公式 2^depth - 1 计算节点个数了。 第二种情况不是满二叉树,但子树一定存在满二叉树,那么可以先找到满二叉树,计算深度,然后计算其他节点
上代码,通用节点计算
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
上代码,完全二叉树节点计算
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
TreeNode leftNode = root.left;
TreeNode rightNode = root.right;
// 定义左右子树深度
int leftDepth = 0, rightDepth = 0;
// 计算左子树深度
while (leftNode != null) {
leftNode = leftNode.left;
leftDepth++;
}
// 计算右子树深度
while (rightNode != null) {
rightNode = rightNode.right;
rightDepth++;
}
// 判断所有子树深度是否一致,如果一致就根据公式计算节点数量
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1;
}
// 非满二叉树,计算其他节点数量
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
重难点
本题使用通用解法并使用后序遍历写法很简单。但是根据题目,要分析的完全二叉树的特点,并利用它的特性计算节点数量,可以有效减少计算时间复杂度
附:学习资料链接
标签:countNodes,16,个数,222,二叉树,计算,root,节点 From: https://www.cnblogs.com/blacksonny/p/17064736.html