参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!
给出一个完全二叉树,求出该树的节点个数。
示例 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
- 题目数据保证输入的树是 完全二叉树
《代码随想录》算法视频公开课:要理解普通二叉树和完全二叉树的区别! | LeetCode:222.完全二叉树节点的数量,相信结合视频再看本篇题解,更有助于大家对本题的理解。
本篇给出按照普通二叉树的求法以及利用完全二叉树性质的求法。
首先按照普通二叉树的逻辑来求。
这道题目的递归法和求二叉树的深度写法类似, 而迭代法,二叉树:层序遍历登场!遍历模板稍稍修改一下,记录遍历的节点数量就可以了。
递归遍历的顺序依然是后序(左右中)。
如果对求二叉树深度还不熟悉的话,看这篇:二叉树:看看这些树的最大深度。
- 确定递归函数的参数和返回值:参数就是传入树的根节点,返回就返回以该节点为根节点二叉树的节点数量,所以返回值为int类型。
代码如下:
int getNodesNum(TreeNode* cur) {
- 确定终止条件:如果为空节点的话,就返回0,表示节点数为0。
代码如下:
if (cur == NULL) return 0;
- 确定单层递归的逻辑:先求它的左子树的节点数量,再求右子树的节点数量,最后取总和再加一 (加1是因为算上当前中间节点)就是目前节点为根节点的节点数量。
代码如下:
int leftNum = getNodesNum(cur->left); // 左
int rightNum = getNodesNum(cur->right); // 右
int treeNum = leftNum + rightNum + 1; // 中
return treeNum;
所以整体C++代码如下:
// 版本一
class Solution {
private:
int getNodesNum(TreeNode* cur) {
if (cur == NULL) return 0;
int leftNum = getNodesNum(cur->left); // 左
int rightNum = getNodesNum(cur->right); // 右
int treeNum = leftNum + rightNum + 1; // 中
return treeNum;
}
public:
int countNodes(TreeNode* root) {
return getNodesNum(root);
}
};
代码精简之后C++代码如下:
// 版本二
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == NULL) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
- 时间复杂度:O(n)
- 空间复杂度:O(log n),算上了递归系统栈占用的空间
网上基本都是这个精简的代码版本,其实不建议大家照着这个来写,代码确实精简,但隐藏了一些内容,连遍历的顺序都看不出来,所以初学者建议学习版本一的代码,稳稳的打基础。
如果对求二叉树层序遍历还不熟悉的话,看这篇:二叉树:层序遍历登场!。
那么只要模板少做改动,加一个变量result,统计节点数量就可以了
class Solution {
public:
int countNodes(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
int result = 0;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
result++; // 记录节点数量
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return result;
}
};
- 时间复杂度:O(n)
- 空间复杂度:O(n)
以上方法都是按照普通二叉树来做的,对于完全二叉树特性不了解的同学可以看这篇 关于二叉树,你该了解这些!,这篇详细介绍了各种二叉树的特性。
在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^(h-1) 个节点。
大家要自己看完全二叉树的定义,很多同学对完全二叉树其实不是真正的懂了。
我来举一个典型的例子如题:
完全二叉树只有两种情况,情况一:就是满二叉树,情况二:最后一层叶子节点没有满。
对于情况一,可以直接用 2^树深度 - 1 来计算,注意这里根节点深度为1。
对于情况二,分别递归左孩子,和右孩子,递归到某一深度一定会有左孩子或者右孩子为满二叉树,然后依然可以按照情况1来计算。
可以看出如果整个树不是满二叉树,就递归其左右孩子,直到遇到满二叉树为止,用公式计算这个子树(满二叉树)的节点数量。
这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢?
在完全二叉树中,如果递归向左遍历的深度等于递归向右遍历的深度,那说明就是满二叉树。如图:
在完全二叉树中,如果递归向左遍历的深度不等于递归向右遍历的深度,则说明不是满二叉树,如图:
那有录友说了,这种情况,递归向左遍历的深度等于递归向右遍历的深度,但也不是满二叉树,如题:
如果这么想,大家就是对 完全二叉树理解有误区了,以上这棵二叉树,它根本就不是一个完全二叉树!
判断其子树是不是满二叉树,如果是则利用公式计算这个子树(满二叉树)的节点数量,如果不是则继续递归,那么 在递归三部曲中,第二部:终止条件的写法应该是这样的:
if (root == nullptr) return 0;
// 开始根据左深度和右深度是否相同来判断该子树是不是满二叉树
TreeNode* left = root->left;
TreeNode* right = root->right;
int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的,为了下面求指数方便
while (left) { // 求左子树深度
left = left->left;
leftDepth++;
}
while (right) { // 求右子树深度
right = right->right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2,返回满足满二叉树的子树节点数量
}
递归三部曲,第三部,单层递归的逻辑:(可以看出使用后序遍历)
int leftTreeNum = countNodes(root->left); // 左
int rightTreeNum = countNodes(root->right); // 右
int result = leftTreeNum + rightTreeNum + 1; // 中
return result;
该部分精简之后代码为:
return countNodes(root->left) + countNodes(root->right) + 1;
最后整体C++代码如下:
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
TreeNode* left = root->left;
TreeNode* right = root->right;
int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的,为了下面求指数方便
while (left) { // 求左子树深度
left = left->left;
leftDepth++;
}
while (right) { // 求右子树深度
right = right->right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2,所以leftDepth初始为0
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
};
- 时间复杂度:O(log n × log n)
- 空间复杂度:O(log n)
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;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int result = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size -- > 0) {
TreeNode cur = queue.poll();
result++;
if (cur.left != null) queue.offer(cur.left);
if (cur.right != null) queue.offer(cur.right);
}
}
return result;
}
}
class Solution {
/**
* 针对完全二叉树的解法
*
* 满二叉树的结点数为:2^depth - 1
*/
public int countNodes(TreeNode root) {
if (root == null) return 0;
TreeNode left = root.left;
TreeNode right = root.right;
int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的,为了下面求指数方便
while (left != null) { // 求左子树深度
left = left.left;
leftDepth++;
}
while (right != null) { // 求右子树深度
right = right.right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2,所以leftDepth初始为0
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
递归法:
class Solution:
def countNodes(self, root: TreeNode) -> int:
return self.getNodesNum(root)
def getNodesNum(self, cur):
if not cur:
return 0
leftNum = self.getNodesNum(cur.left) #左
rightNum = self.getNodesNum(cur.right) #右
treeNum = leftNum + rightNum + 1 #中
return treeNum
递归法:精简版
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root:
return 0
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
迭代法:
import collections
class Solution:
def countNodes(self, root: TreeNode) -> int:
queue = collections.deque()
if root:
queue.append(root)
result = 0
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
result += 1 #记录节点数量
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
完全二叉树
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root:
return 0
left = root.left
right = root.right
leftDepth = 0 #这里初始为0是有目的的,为了下面求指数方便
rightDepth = 0
while left: #求左子树深度
left = left.left
leftDepth += 1
while right: #求右子树深度
right = right.right
rightDepth += 1
if leftDepth == rightDepth:
return (2 << leftDepth) - 1 #注意(2<<1) 相当于2^2,所以leftDepth初始为0
return self.countNodes(root.left) + self.countNodes(root.right) + 1
完全二叉树写法2
class Solution: # 利用完全二叉树特性
def countNodes(self, root: TreeNode) -> int:
if not root: return 0
count = 1
left = root.left; right = root.right
while left and right:
count+=1
left = left.left; right = right.right
if not left and not right: # 如果同时到底说明是满二叉树,反之则不是
return 2**count-1
return 1+self.countNodes(root.left)+self.countNodes(root.right)
完全二叉树写法3
class Solution: # 利用完全二叉树特性
def countNodes(self, root: TreeNode) -> int:
if not root: return 0
count = 0
left = root.left; right = root.right
while left and right:
count+=1
left = left.left; right = right.right
if not left and not right: # 如果同时到底说明是满二叉树,反之则不是
return (2<<count)-1
return 1+self.countNodes(root.left)+self.countNodes(root.right)
递归版本
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
//本题直接就是求有多少个节点,无脑存进结果变量就行了。
func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
res := 1
if root.Right != nil {
res += countNodes(root.Right)
}
if root.Left != nil {
res += countNodes(root.Left)
}
return res
}
利用完全二叉树特性的递归解法
func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
leftH, rightH := 0, 0
leftNode := root.Left
rightNode := root.Right
for leftNode != nil {
leftNode = leftNode.Left
leftH++
}
for rightNode != nil {
rightNode = rightNode.Right
rightH++
}
if leftH == rightH {
return (2 << leftH) - 1
}
return countNodes(root.Left) + countNodes(root.Right) + 1
}
迭代法
func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
q := list.New()
q.PushBack(root)
res := 0
for q.Len() > 0 {
n := q.Len()
for i := 0; i < n; i++ {
node := q.Remove(q.Front()).(*TreeNode)
if node.Left != nil {
q.PushBack(node.Left)
}
if node.Right != nil {
q.PushBack(node.Right)
}
res++
}
}
return res
}
递归版本
var countNodes = function(root) {
//递归法计算二叉树节点数
// 1. 确定递归函数参数
const getNodeSum = function(node) {
//2. 确定终止条件
if(node === null) {
return 0;
}
//3. 确定单层递归逻辑
let leftNum = getNodeSum(node.left);
let rightNum = getNodeSum(node.right);
return leftNum + rightNum + 1;
}
return getNodeSum(root);
};
迭代(层序遍历)版本
var countNodes = function(root) {
//层序遍历
let queue = [];
if(root === null) {
return 0;
}
queue.push(root);
let nodeNums = 0;
while(queue.length) {
let length = queue.length;
while(length--) {
let node = queue.shift();
nodeNums++;
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
return nodeNums;
};
利用完全二叉树性质
var countNodes = function(root) {
//利用完全二叉树的特点
if(root === null) {
return 0;
}
let left = root.left;
let right = root.right;
let leftDepth = 0, rightDepth = 0;
while(left) {
left = left.left;
leftDepth++;
}
while(right) {
right = right.right;
rightDepth++;
}
if(leftDepth == rightDepth) {
return Math.pow(2, leftDepth+1) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
};
递归法
function countNodes(root: TreeNode | null): number {
if (root === null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
};
迭代法
function countNodes(root: TreeNode | null): number {
let helperQueue: TreeNode[] = [];
let resCount: number = 0;
let tempNode: TreeNode;
if (root !== null) helperQueue.push(root);
while (helperQueue.length > 0) {
for (let i = 0, length = helperQueue.length; i < length; i++) {
tempNode = helperQueue.shift()!;
resCount++;
if (tempNode.left) helperQueue.push(tempNode.left);
if (tempNode.right) helperQueue.push(tempNode.right);
}
}
return resCount;
};
利用完全二叉树性质
function countNodes(root: TreeNode | null): number {
if (root === null) return 0;
let left: number = 0,
right: number = 0;
let curNode: TreeNode | null= root;
while (curNode !== null) {
left++;
curNode = curNode.left;
}
curNode = root;
while (curNode !== null) {
right++;
curNode = curNode.right;
}
if (left === right) {
return 2 ** left - 1;
}
return 1 + countNodes(root.left) + countNodes(root.right);
};
递归法
int countNodes(struct TreeNode* root) {
//若传入结点不存在,返回0
if(!root)
return 0;
//算出左右子树的结点总数
int leftCount = countNodes(root->left);
int rightCount = countNodes(root->right);
//返回左右子树结点总数+1
return leftCount + rightCount + 1;
}
int countNodes(struct TreeNode* root){
return getNodes(root);
}
迭代法
int countNodes(struct TreeNode* root){
//记录结点总数
int totalNum = 0;
//开辟栈空间
struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 100);
int stackTop = 0;
//如果root结点不为NULL,则将其入栈。若为NULL,则不会进入遍历,返回0
if(root)
stack[stackTop++] = root;
//若栈中有结点存在,则进行遍历
while(stackTop) {
//取出栈顶元素
struct TreeNode* tempNode = stack[--stackTop];
//结点总数+1
totalNum++;
//若栈顶结点有左右孩子,将它们入栈
if(tempNode->left)
stack[stackTop++] = tempNode->left;
if(tempNode->right)
stack[stackTop++] = tempNode->right;
}
return totalNum;
}
满二叉树
int countNodes(struct TreeNode* root){
if(!root)
return 0;
int leftDepth = 0;
int rightDepth = 0;
struct TreeNode* rightNode = root->right;
struct TreeNode* leftNode = root->left;
//求出左子树深度
while(leftNode) {
leftNode = leftNode->left;
leftDepth++;
}
//求出右子树深度
while(rightNode) {
rightNode = rightNode->right;
rightDepth++;
}
//若左右子树深度相同,为满二叉树。结点个数为2^height-1
if(rightDepth == leftDepth) {
return (2 << leftDepth) - 1;
}
//否则返回左右子树的结点个数+1
return countNodes(root->right) + countNodes(root->left) + 1;
}
递归
func countNodes(_ root: TreeNode?) -> Int {
return _countNodes(root)
}
func _countNodes(_ root: TreeNode?) -> Int {
guard let root = root else {
return 0
}
let leftCount = _countNodes(root.left)
let rightCount = _countNodes(root.right)
return 1 + leftCount + rightCount
}
层序遍历
func countNodes(_ root: TreeNode?) -> Int {
guard let root = root else {
return 0
}
var res = 0
var queue = [TreeNode]()
queue.append(root)
while !queue.isEmpty {
let size = queue.count
for _ in 0 ..< size {
let node = queue.removeFirst()
res += 1
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
}
return res
}
利用完全二叉树性质
func countNodes(_ root: TreeNode?) -> Int {
guard let root = root else {
return 0
}
var leftNode = root.left
var rightNode = root.right
var leftDepth = 0
var rightDepth = 0
while leftNode != nil {
leftNode = leftNode!.left
leftDepth += 1
}
while rightNode != nil {
rightNode = rightNode!.right
rightDepth += 1
}
if leftDepth == rightDepth {
return (2 << leftDepth) - 1
}
return countNodes(root.left) + countNodes(root.right) + 1
}
递归:
object Solution {
def countNodes(root: TreeNode): Int = {
if(root == null) return 0
1 + countNodes(root.left) + countNodes(root.right)
}
}
层序遍历:
object Solution {
import scala.collection.mutable
def countNodes(root: TreeNode): Int = {
if (root == null) return 0
val queue = mutable.Queue[TreeNode]()
var node = 0
queue.enqueue(root)
while (!queue.isEmpty) {
val len = queue.size
for (i <- 0 until len) {
node += 1
val curNode = queue.dequeue()
if (curNode.left != null) queue.enqueue(curNode.left)
if (curNode.right != null) queue.enqueue(curNode.right)
}
}
node
}
}
利用完全二叉树性质:
object Solution {
def countNodes(root: TreeNode): Int = {
if (root == null) return 0
var leftNode = root.left
var rightNode = root.right
// 向左向右往下探
var leftDepth = 0
while (leftNode != null) {
leftDepth += 1
leftNode = leftNode.left
}
var rightDepth = 0
while (rightNode != null) {
rightDepth += 1
rightNode = rightNode.right
}
// 如果相等就是一个满二叉树
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1
}
// 如果不相等就不是一个完全二叉树,继续向下递归
countNodes(root.left) + countNodes(root.right) + 1
}
}
递归
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
if root.is_none() {
return 0;
}
1 + Self::count_nodes(Rc::clone(root.as_ref().unwrap()).borrow().left.clone())
+ Self::count_nodes(root.unwrap().borrow().right.clone())
}
}
迭代
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
pub fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let mut res = 0;
let mut queue = VecDeque::new();
if root.is_some() {
queue.push_back(root);
}
while !queue.is_empty() {
for _ in 0..queue.len() {
let node = queue.pop_front().unwrap().unwrap();
if node.borrow().left.is_some() {
queue.push_back(node.borrow().left.clone());
}
if node.borrow().right.is_some() {
queue.push_back(node.borrow().right.clone());
}
res += 1;
}
}
res
}
}
// 递归
public int CountNodes(TreeNode root)
{
if (root == null) return 0;
var left = root.left;
var right = root.right;
int leftDepth = 0, rightDepth = 0;
while (left != null)
{
left = left.left;
leftDepth++;
}
while (right != null)
{
right = right.right;
rightDepth++;
}
if (leftDepth == rightDepth)
return (int)Math.Pow(2, leftDepth+1) - 1;
return CountNodes(root.left) + CountNodes(root.right) + 1;
}