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

题目-中等难度

中等
1K
相关企业
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例

示例 1：

输入：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) 的简单解决方案。你可以设计一个更快的算法吗？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/summary-ranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. BFS

时间
60ms
击败 71.14%使用 Python 的用户
内存
27.93MB
击败 7.91%使用 Python 的用户

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        li = [root]
        res = 0
        while li:
            for _ in range(len(li)):
                a = li.pop()
                if a:
                    res += 1
                if a and a.left:
                    li.append(a.left)
                if a and a.right:
                    li.append(a.right)

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2. dfs

时间
56ms
击败 84.74%使用 Python 的用户
内存
27.58MB
击败 79.96%使用 Python 的用户

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 迭代
        def dfs(node):
        	# 如果节点不存在, 返回0
            if not node:
                return 0
            # 迭代统计左节点
            left = dfs(node.left)
            right = dfs(node.right)
            # 统计个数, 当前节点下左右节点各有多少节点+当前节点
            return left+right+1
        return dfs(root)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23