应用题-二叉树专题-完全二叉树的节点个数
- 版权声明：本站原创文章，于2026-03-24，由 管理员 发表。
- 转载请注明： 应用题-二叉树专题-完全二叉树的节点个数 | CodeGarden
**写法1**
```python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root: return 0
self.count = 0
def count_( r ):
if not r: return
self.count += 1
count_( r.left )
count_ ( r.right )
count_( root )
return self.count
```
**写法2**
```python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root: return 0
c1 = self.countNodes( root.left )
c2 = self.countNodes( root.right )
return c1 + c2 + 1
```
**写法3**
```python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
# 利用完全二叉树的性质
if not root: return 0
l, r = root.left, root.right
h1, h2 = 0, 0
while l:
l = l.left
h1 += 1
while r:
r = r.right
h2 += 1
if h1 == h2:
# 满二叉树
return ( 2 << h1 ) - 1
# 完全二叉树的左右子树也是完全二叉树
# 递归下来 只有一个节点不是满二叉树
return self.countNodes( root.left ) + self.countNodes( root.right ) + 1
```