当前位置： 面试刷题>> 完全二叉树的节点个数(经典算法150题)
### 题目描述
给定一棵完全二叉树的根节点，请编写一个函数来计算这棵完全二叉树中节点的个数。
**注意**：
- 完全二叉树的定义是：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
### 示例
假设我们有以下完全二叉树：
```
1
/ \
2 3
/ \ \
4 5 6
```
该完全二叉树有 6 个节点。
### PHP 示例代码
```php
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
function countNodes($root) {
if ($root == null) {
return 0;
}
$leftHeight = 0;
$rightHeight = 0;
$leftNode = $root->left;
$rightNode = $root->right;
// 计算左子树的高度
while ($leftNode != null) {
$leftHeight++;
$leftNode = $leftNode->left;
}
// 计算右子树的高度
while ($rightNode != null) {
$rightHeight++;
$rightNode = $rightNode->right;
}
// 如果左右子树高度相同，说明左子树是满二叉树
if ($leftHeight == $rightHeight) {
return (1 << $leftHeight) - 1 + countNodes($root->right);
} else {
// 否则，右子树是满二叉树（少一层）
return (1 << $rightHeight) - 1 + countNodes($root->left);
}
}
// 示例用法
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(3);
$root->left->left = new TreeNode(4);
$root->left->right = new TreeNode(5);
$root->right->right = new TreeNode(6);
echo countNodes($root); // 输出 6
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def countNodes(root):
if not root:
return 0
left_height = 0
right_height = 0
left_node = root.left
right_node = root.right
# 计算左子树的高度
while left_node:
left_height += 1
left_node = left_node.left
# 计算右子树的高度
while right_node:
right_height += 1
right_node = right_node.right
# 如果左右子树高度相同，说明左子树是满二叉树
if left_height == right_height:
return (1 << left_height) - 1 + countNodes(root.right)
else:
# 否则，右子树是满二叉树（少一层）
return (1 << right_height) - 1 + countNodes(root.left)
# 示例用法
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
print(countNodes(root)) # 输出 6
```
### JavaScript 示例代码
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function countNodes(root) {
if (!root) {
return 0;
}
let leftHeight = 0;
let rightHeight = 0;
let leftNode = root.left;
let rightNode = root.right;
// 计算左子树的高度
while (leftNode) {
leftHeight++;
leftNode = leftNode.left;
}
// 计算右子树的高度
while (rightNode) {
rightHeight++;
rightNode = rightNode.right;
}
// 如果左右子树高度相同，说明左子树是满二叉树
if (leftHeight === rightHeight) {
return (1 << leftHeight) - 1 + countNodes(root.right);
} else {
// 否则，右子树是满二叉树（少一层）
return (1 << rightHeight) - 1 + countNodes(root.left);
}
}
// 示例用法
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);
console.log(countNodes(root)); // 输出 6
```
以上代码通过递归和位运算高效地计算了完全二叉树的节点个数。