222. Count Complete Tree Nodes (Medium) - TengnanYao/daily_leetcode GitHub Wiki

# 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 getDepth(root):
            if not root:
                return 0
            return getDepth(root.left) + 1
        
        self.result = 0
        def count(root):
            if root:
                l, r = getDepth(root.left), getDepth(root.right)
                self.result += 2 ** r
                if l == r:
                    count(root.right)
                else:
                    count(root.left)
        count(root)
        return self.result
    
        # # O(n) solution
        # if not root:
        #     return 0
        # return self.countNodes(root.left) + self.countNodes(root.right) + 1