LeetCode

Appearance

222. Count Complete Tree Nodes ​

题目 ​

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

 

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

 

Constraints:

  • The number of nodes in the tree is in the range [0, 5 * 104].
  • 0 <= Node.val <= 5 * 104
  • The tree is guaranteed to be complete.
Related Topics
  • 位运算
  • 树
  • 二分查找
  • 二叉树

  • 👍 1258
  • 👎 0

    • 思路 ​

    二叉完全树，又称为 complete tree， 自上向下，自左向右依次添满整个树形结构，整个树只有最末的一层可能未填满

    本题要求在 O(N) 时间复杂度以下完成，故先放弃暴力遍历的方法

    complete tree = sub complete tree + full tree

    根据这个特性可以进行二叉树完全树简化处理，分为 sub complete tree 和 full tree 的并行处理，减少计算量

    解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
# 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: Optional[TreeNode]) -> int:
        hl, hr = 0, 0
        noder, nodel = root, root
        while nodel:
            nodel = nodel.left
            hl += 1

        while noder:
            noder = noder.right
            hr += 1

        if hr == hl:
            return int(math.pow(2, hl) - 1)


        return  self.countNodes(root.left) + self.countNodes(root.right) + 1
        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(logN * logN)
    • 空间复杂度 O(N)