该题解采用了递归的思路,利用完全二叉树的性质来优化计算节点个数的过程。首先通过 get_height 函数递归计算完全二叉树的高度。如果高度小于等于1,直接返回高度作为节点个数。否则,通过判断右子树的高度是否等于总高度减2,如果是,说明左子树是一个满二叉树,可以直接计算左子树的节点数,再加上右子树递归计算的节点数;如果右子树高度不等于总高度减2,说明右子树是一个满二叉树,可以直接计算右子树的节点数,再加上左子树递归计算的节点数。通过这样的方式,可以避免遍历整棵树,从而降低时间复杂度。
时间复杂度: O((log n)^2)
空间复杂度: O(log n)
# 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: TreeNode) -> int:
def get_height(root):
if root is None:
return 0
return get_height(root.left) + 1
height = get_height(root)
if height <= 1:
return height
# 判断右子树的高度是否等于总高度减2
if get_height(root.right) == height - 2:
# 如果是,左子树是满二叉树,计算左子树的节点数,再加上右子树递归计算的节点数
return (1 << (height - 2)) + self.countNodes(root.left)
else:
# 如果不是,右子树是满二叉树,计算右子树的节点数,再加上左子树递归计算的节点数
return (1 << (height - 1)) + self.countNodes(root.right)