[222] Count Complete Tree Nodes

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

• algorithms
• Medium (29.44%)
• Source Code: 222.count-complete-tree-nodes.py
• Total Accepted: 114.2K
• Total Submissions: 350.6K
• Testcase Example: '[1,2,3,4,5,6]'

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

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root: return 0
        cnt = [0]
        self.do_the_cnt(root, cnt)

        return cnt[0]

    def do_the_cnt(self, root, cnt):
        cnt[0] += 1
        if root.left:
            self.do_the_cnt(root.left, cnt)
        if root.right:
            self.do_the_cnt(root.right, cnt)