mirror of
https://github.com/youngyangyang04/leetcode-master.git
synced 2026-02-02 18:39:09 +08:00
895 lines
24 KiB
Markdown
Executable File
895 lines
24 KiB
Markdown
Executable File
* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
|
||
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
|
||
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)
|
||
|
||
|
||
# 222.完全二叉树的节点个数
|
||
|
||
[力扣题目链接](https://leetcode.cn/problems/count-complete-tree-nodes/)
|
||
|
||
给出一个完全二叉树，求出该树的节点个数。
|
||
|
||
示例 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
|
||
* 题目数据保证输入的树是 完全二叉树
|
||
|
||
## 算法公开课
|
||
|
||
**[《代码随想录》算法视频公开课](https://programmercarl.com/other/gongkaike.html)：[要理解普通二叉树和完全二叉树的区别！ | LeetCode：222.完全二叉树节点的数量](https://www.bilibili.com/video/BV1eW4y1B7pD)，相信结合视频再看本篇题解，更有助于大家对本题的理解**。
|
||
|
||
|
||
## 思路
|
||
|
||
|
||
本篇给出按照普通二叉树的求法以及利用完全二叉树性质的求法。
|
||
|
||
### 普通二叉树
|
||
|
||
首先按照普通二叉树的逻辑来求。
|
||
|
||
这道题目的递归法和求二叉树的深度写法类似， 而迭代法，[二叉树：层序遍历登场！](https://programmercarl.com/0102.二叉树的层序遍历.html)遍历模板稍稍修改一下，记录遍历的节点数量就可以了。
|
||
|
||
递归遍历的顺序依然是后序（左右中）。
|
||
|
||
#### 递归
|
||
|
||
如果对求二叉树深度还不熟悉的话，看这篇：[二叉树：看看这些树的最大深度](https://programmercarl.com/0104.二叉树的最大深度.html)。
|
||
|
||
1. 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。
|
||
|
||
代码如下：
|
||
```CPP
|
||
int getNodesNum(TreeNode* cur) {
|
||
```
|
||
|
||
2. 确定终止条件：如果为空节点的话，就返回0，表示节点数为0。
|
||
|
||
代码如下：
|
||
|
||
```CPP
|
||
if (cur == NULL) return 0;
|
||
```
|
||
|
||
3. 确定单层递归的逻辑：先求它的左子树的节点数量，再求右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。
|
||
|
||
代码如下：
|
||
|
||
```CPP
|
||
int leftNum = getNodesNum(cur->left); // 左
|
||
int rightNum = getNodesNum(cur->right); // 右
|
||
int treeNum = leftNum + rightNum + 1; // 中
|
||
return treeNum;
|
||
```
|
||
|
||
所以整体C++代码如下：
|
||
|
||
```CPP
|
||
// 版本一
|
||
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++代码如下：
|
||
```CPP
|
||
// 版本二
|
||
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)，算上了递归系统栈占用的空间
|
||
|
||
**网上基本都是这个精简的代码版本，其实不建议大家照着这个来写，代码确实精简，但隐藏了一些内容，连遍历的顺序都看不出来，所以初学者建议学习版本一的代码，稳稳的打基础**。
|
||
|
||
|
||
#### 迭代
|
||
|
||
如果对求二叉树层序遍历还不熟悉的话，看这篇：[二叉树：层序遍历登场！](https://programmercarl.com/0102.二叉树的层序遍历.html)。
|
||
|
||
那么只要模板少做改动，加一个变量result，统计节点数量就可以了
|
||
|
||
```CPP
|
||
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)
|
||
|
||
### 完全二叉树
|
||
|
||
以上方法都是按照普通二叉树来做的，对于完全二叉树特性不了解的同学可以看这篇 [关于二叉树，你该了解这些！](https://programmercarl.com/二叉树理论基础.html)，这篇详细介绍了各种二叉树的特性。
|
||
|
||
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
|
||
|
||
**大家要自己看完全二叉树的定义，很多同学对完全二叉树其实不是真正的懂了。**
|
||
|
||
我来举一个典型的例子如题：
|
||
|
||
<img src='https://file1.kamacoder.com/i/algo/20200920221638903-20230310123444151.png' width=600> </img>
|
||
|
||
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
|
||
|
||
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
|
||
|
||
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
|
||
|
||
完全二叉树（一）如图：
|
||
|
||
|
||
完全二叉树（二）如图：
|
||
|
||
|
||
可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。
|
||
|
||
这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？
|
||
|
||
在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。如图：
|
||
|
||
|
||
|
||
在完全二叉树中，如果递归向左遍历的深度不等于递归向右遍历的深度，则说明不是满二叉树，如图：
|
||
|
||
|
||
|
||
那有录友说了，这种情况，递归向左遍历的深度等于递归向右遍历的深度，但也不是满二叉树，如题：
|
||
|
||
|
||
|
||
如果这么想，大家就是对 完全二叉树理解有误区了，**以上这棵二叉树，它根本就不是一个完全二叉树**！
|
||
|
||
判断其子树是不是满二叉树，如果是则利用公式计算这个子树（满二叉树）的节点数量，如果不是则继续递归，那么 在递归三部曲中，第二部：终止条件的写法应该是这样的：
|
||
|
||
```CPP
|
||
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，返回满足满二叉树的子树节点数量
|
||
}
|
||
```
|
||
|
||
递归三部曲，第三部，单层递归的逻辑：（可以看出使用后序遍历）
|
||
|
||
```CPP
|
||
int leftTreeNum = countNodes(root->left); // 左
|
||
int rightTreeNum = countNodes(root->right); // 右
|
||
int result = leftTreeNum + rightTreeNum + 1; // 中
|
||
return result;
|
||
```
|
||
|
||
该部分精简之后代码为：
|
||
|
||
```CPP
|
||
return countNodes(root->left) + countNodes(root->right) + 1;
|
||
```
|
||
|
||
最后整体C++代码如下：
|
||
|
||
```CPP
|
||
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)
|
||
|
||
## 其他语言版本
|
||
|
||
### Java:
|
||
```java
|
||
class Solution {
|
||
// 通用递归解法
|
||
public int countNodes(TreeNode root) {
|
||
if(root == null) {
|
||
return 0;
|
||
}
|
||
return countNodes(root.left) + countNodes(root.right) + 1;
|
||
}
|
||
}
|
||
```
|
||
```java
|
||
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;
|
||
}
|
||
}
|
||
```
|
||
```java
|
||
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;
|
||
}
|
||
}
|
||
```
|
||
|
||
### Python:
|
||
|
||
递归法：
|
||
```python
|
||
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
|
||
```
|
||
|
||
递归法：精简版
|
||
```python
|
||
class Solution:
|
||
def countNodes(self, root: TreeNode) -> int:
|
||
if not root:
|
||
return 0
|
||
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
|
||
```
|
||
|
||
迭代法：
|
||
```python
|
||
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
|
||
```
|
||
|
||
完全二叉树
|
||
```python
|
||
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
|
||
```python
|
||
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
|
||
```python
|
||
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)
|
||
```
|
||
|
||
### Go:
|
||
|
||
递归版本
|
||
|
||
```go
|
||
/**
|
||
* 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
|
||
}
|
||
```
|
||
|
||
利用完全二叉树特性的递归解法
|
||
```go
|
||
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
|
||
}
|
||
```
|
||
|
||
迭代法
|
||
|
||
```go
|
||
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
|
||
}
|
||
```
|
||
|
||
### JavaScript:
|
||
|
||
递归版本
|
||
```javascript
|
||
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);
|
||
};
|
||
```
|
||
|
||
迭代(层序遍历)版本
|
||
```javascript
|
||
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;
|
||
};
|
||
```
|
||
|
||
利用完全二叉树性质
|
||
```javascript
|
||
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;
|
||
};
|
||
```
|
||
|
||
### TypeScrpt:
|
||
|
||
> 递归法
|
||
|
||
```typescript
|
||
function countNodes(root: TreeNode | null): number {
|
||
if (root === null) return 0;
|
||
return 1 + countNodes(root.left) + countNodes(root.right);
|
||
};
|
||
```
|
||
|
||
> 迭代法
|
||
|
||
```typescript
|
||
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;
|
||
};
|
||
```
|
||
|
||
> 利用完全二叉树性质
|
||
|
||
```typescript
|
||
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);
|
||
};
|
||
```
|
||
|
||
### C:
|
||
|
||
递归法
|
||
```c
|
||
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);
|
||
}
|
||
```
|
||
|
||
迭代法
|
||
```c
|
||
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;
|
||
}
|
||
```
|
||
|
||
满二叉树
|
||
```c
|
||
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;
|
||
}
|
||
```
|
||
|
||
### Swift:
|
||
|
||
> 递归
|
||
```swift
|
||
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
|
||
}
|
||
```
|
||
|
||
> 层序遍历
|
||
```Swift
|
||
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
|
||
}
|
||
```
|
||
|
||
> 利用完全二叉树性质
|
||
```Swift
|
||
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
|
||
}
|
||
```
|
||
|
||
### Scala:
|
||
|
||
递归:
|
||
```scala
|
||
object Solution {
|
||
def countNodes(root: TreeNode): Int = {
|
||
if(root == null) return 0
|
||
1 + countNodes(root.left) + countNodes(root.right)
|
||
}
|
||
}
|
||
```
|
||
|
||
层序遍历:
|
||
```scala
|
||
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
|
||
}
|
||
}
|
||
```
|
||
|
||
利用完全二叉树性质:
|
||
```scala
|
||
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
|
||
}
|
||
}
|
||
```
|
||
|
||
### Rust:
|
||
|
||
递归
|
||
```rust
|
||
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())
|
||
}
|
||
}
|
||
```
|
||
|
||
迭代
|
||
```rust
|
||
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
|
||
}
|
||
}
|
||
```
|
||
### C#
|
||
```csharp
|
||
// 递归
|
||
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;
|
||
|
||
}
|
||
```
|
||
|
||
|