0222._count_complete_tree_nodes.md

222. Count Complete Tree Nodes

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/count-complete-tree-nodes/

内容描述

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, 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.

Example:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

无脑遍历算个数,beats 49.18%

class Solution:
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        res = []
        if not root:
            return 0
        
        stack = []
        node = root
        while node or (len(stack) > 0):
            if node:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                res.append(node.val)
                node = node.right
        return len(res)

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

递归

class Solution:
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

思路 3 - 时间复杂度: O(lgN * lgN)- 空间复杂度: O(1)******

求出正常的左右子树的高度lh和rh，然后

• 如果相等的话就知道左边子树肯定是满的，一共有2 ** lh个node，先算出来然后递归计算右边子树的node个数；
• 同理lh和rh不相等的话，就知道右边子树是满的，一共有2 ** rh个node，先算出来然后递归计算右边子树的node个数；

class Solution:
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        lh = self.height(root.left)
        rh = self.height(root.right)
        if lh == rh:
            return 2 ** lh + self.countNodes(root.right)
        else:
            return 2 ** rh + self.countNodes(root.left)
            
    def height(self, root):
        if not root:
            return 0
        return 1 + max(self.height(root.left), self.height(root.right))

思路 4 - 时间复杂度: O(lgN * lgN)- 空间复杂度: O(1)******

既然说了是 complete binary tree，那么必然有特性可用，complete binary tree的特性是除了最后一层，之前的就是perfect tree.

所以寻找左子树的最左边的高度left_most_height和右子树的最右边的node高度right_most_height，如果相同就是perfect tree，高度2^h - 1， 否则递归的来看左子树和右子树

beats 94.85%

class Solution:
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0

        p, q = root, root

        lmh, rmh = 0, 0
        while p:
            p = p.left
            lmh += 1
        while q:
            q = q.right
            rmh += 1

        if lmh == rmh:
            return 2 ** lmh - 1
        else:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)