Count Complete Tree Nodes LeetCode solution in Python

1
class Solution:
2
    # @param {TreeNode} root
3
    # @return {integer}
4
    def countNodes(self, root):
5
        if not root:
6
            return 0
7
        leftDepth = self.getDepth(root.left)
8
        rightDepth = self.getDepth(root.right)
9
        if leftDepth == rightDepth:
10
            return pow(2, leftDepth) + self.countNodes(root.right)
11
        else:
12
            return pow(2, rightDepth) + self.countNodes(root.left)
13

14
    def getDepth(self, root):
15
        if not root:
16
            return 0
17
        return 1 + self.getDepth(root.left)