222. 完全二叉树的节点个数

Difficulty
Medium
Tags
二叉树
URL
https://leetcode-cn.com/problems/count-complete-tree-nodes/
Star
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
notion imagenotion image
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
提示：
  • 树中节点的数目范围是[0, 5 * 104]
  • 0 <= Node.val <= 5 * 104
  • 题目数据保证输入的树是 完全二叉树
进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

法1 递归

思路
采用递归法遍历二叉树，分为左子树 右子树。
题解
# 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:
        if root is None:
            return 0
        left_count = self.countNodes(root.left)
        right_count = self.countNodes(root.right)
        return left_count + right_count + 1

法2 层次遍历

思路
采用层次遍历，将节点逐个遍历，然后统计节点个数
具体实现：利用队列来实现层次遍历，然后在出队的时候 result += 1
题解
# 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:
        result = 0
        if root is None:
            return result
        queue = []
        queue.append(root)
        
        while len(queue) > 0:
            temp_node = queue.pop(0)
            result += 1 # 出队列的时候 +1 
            if temp_node.left:
                queue.append(temp_node.left)
            if temp_node.right:
                queue.append(temp_node.right)

        return result

法3：递归 + 满二叉树的特性

思路
以上两种方法均是按照普通二叉树遍历来统计节点个数的。
利用满二叉树的特性：空节点只在最后一层的最右边。且
所以用以下语句可以判断子树是否为满二叉树
left_tree = root.left
right_tree = root.right
left_length = 1
right_length = 1
while(left_tree):
    left_tree = left_tree.left
    left_length += 1
while(right_tree):
    right_tree = right_tree.right
    right_length += 1
if left_length == right_length:
		# 是满二叉树
所以递归的查找满二叉子树 ，遇到满二叉树直接返回
该递归的最小子问题即为 满二叉树。所以基线条件为 子树为满二叉树
题解
# 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:
        if root is None:
            return 0

        depth = self.getdepth(root)
        if depth > 0:
            return 2 ** depth - 1
        else:
            return self.countNodes(root.left) + \
                    self.countNodes(root.right) + 1


    def getdepth(self, root):
        # 判断是否为完全二叉树，如果是完全二叉树，返回深度，否则返回0
        left_depth, right_depth = 1, 1
        left_node, right_node = root.left, root.righ

        while left_node:
            left_node = left_node.left
            left_depth += 1
        
        while right_node:
            right_node = right_node.right
            right_depth += 1

        return left_depth if left_depth == right_depth else 0

法 4

思路
判断左右子树的高度:
  • 如果相等 说明左子树是满二叉树,
    • 然后进一步判断右子树的节点数(最后一层最后出现的节点必然在右子树中)
  • 如果不等说明 右子树是深度小于左子树的满二叉树
    • 然后进一步判断左子树的节点数(最后一层最后出现的节点必然在左子树中)
题解
# 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:
        if root is None:
            return 0
        
        '''
        完全二叉树的高度可以直接通过不断地访问左子树就可以获取
        判断左右子树的高度: 
            如果相等说明左子树是满二叉树, 
                然后进一步判断右子树的节点数(最后一层最后出现的节点必然在右子树中)
            如果不等说明右子树是深度小于左子树的满二叉树, 
                然后进一步判断左子树的节点数(最后一层最后出现的节点必然在左子树中)
        '''

        l = self.getdepth(root.left)
        r = self.getdepth(root.right)
        # 说明 左子树为满二叉树
        if l == r:
            return 1 + 2 ** l - 1 + self.countNodes(root.right)
        # 说明右子树为满二叉树
        else:
            return 1 + 2 ** r - 1 + self.countNodes(root.left)


    def getdepth(self, root):
        res = 0
        while root:
            root = root.left
            res += 1
        return res