给你一颗二叉树,请你求出该二叉树的结点总数。
时间: 2024-01-23 08:07:10 浏览: 70
好的,这是一道经典的二叉树问题。我可以给你一个递归的解法。
首先,如果二叉树为空,节点数为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$ 是二叉树的节点数。
阅读全文