给你一颗二叉树,请你求出该二叉树的结点总数。
时间: 2024-01-23 19:07:10 浏览: 27
好的,这是一道经典的二叉树问题。我可以给你一个递归的解法。
首先,如果二叉树为空,节点数为0。否则,可以把二叉树拆分成左子树和右子树两部分,分别求出它们的节点数,然后加上根节点,即可得到整棵树的节点数。具体的实现可以参考下面的代码:
```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def countNodes(root: TreeNode) -> int:
if not root:
return 0
left_height = get_height(root.left)
right_height = get_height(root.right)
if left_height == right_height:
# 左子树是一棵满二叉树,右子树是一棵普通二叉树
return (1 << left_height) + countNodes(root.right)
else:
# 右子树是一棵满二叉树,左子树是一棵普通二叉树
return (1 << right_height) + countNodes(root.left)
def get_height(root: TreeNode) -> int:
height = 0
while root:
height += 1
root = root.left
return height
```
其中,`countNodes` 函数用于计算二叉树的节点数,`get_height` 函数用于计算一棵满二叉树的高度。这个算法的时间复杂度是 $O(\log^2 n)$,其中 $n$ 是二叉树的节点数。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)